#include "routing1.h"

Routing1 *thisRouting;

Routing1::Routing1(Cell *cell, QPlainTextEdit *debug)
{
    this->cell = cell;
    this->debug = debug;

    thisRouting = this;
}

void Routing1::route()
{
    resetRouting();
    internRouting();
    routeBandToGate();
    bandRouting();
    insertM1ToContacts();
    insertDiffToContacts();
    routeGates();
    movePolyIn();
    routeVccGnd();
    fixMetal2Height();
    fillNonGapSpaceWithDiff();
    insertGatePolyContacts();
    solveDesignRulesConflicts();
    //replaceMetal2WithMetal1();
    //insertPins();
}

qreal Routing1::translateMetal(Metal* m, QList<Metal*> *items, qreal dx, qreal rule, QString direction)
{
    qreal previousX = m->x();

    if(direction.compare("LEFT") == 0)
        dx *= -1;

    m->setX(m->x() + dx);

    Metal* collidingMetal = getCollidingMetal(m,items,rule);

    if(collidingMetal && direction.compare("LEFT") == 0 && collidingMetal->x() < m->x())
    {
        m->setX(collidingMetal->x() + collidingMetal->bottomRight.x() + rule);

        if(m->x() > previousX)
            m->setX(previousX);
    }
    else if(collidingMetal && direction.compare("RIGHT") == 0 && collidingMetal->x() > m->x())
    {
        m->setX(collidingMetal->x() - m->bottomRight.x() - rule);

        if(m->x() < previousX)
            m->setX(previousX);
    }

    return qAbs(previousX - m->x());
}

void Routing1::translateTransistors(QList<Transistor*> *transistors, int initialIndex, qreal dx)
{
    foreach(Transistor* t, *(transistors))
        if(t->posIndex >= initialIndex)
        {
            t->routedPos.setX(t->x() + dx);
            t->setX(t->x() + dx);
        }
}

void Routing1::translateTransistors(Transistor* t, qreal dx)
{
    translateTransistors(cell->pTransistors, t->posIndex, dx);
    translateTransistors(cell->nTransistors, t->posIndex, dx);

    foreach(Metal* po, *(cell->poItems))
    {
        if(po->porpouse == 3)
        {
            Transistor* poT = ((Transistor*)(po->linkedTransistors->first()));

            if(poT->posIndex >= t->posIndex)
                po->setX(poT->x() - Rules::getRule("PO.W.1a")/2);
        }
    }

    foreach(Metal* po, *(cell->poItems))
    {
        if(po->porpouse == 4)
        {
            Transistor* poT = ((Transistor*)(po->linkedMetal->first()->linkedTransistors->first()));

            if(poT->posIndex >= t->posIndex)
            {
                qreal contactWidth = Rules::getRule("CO.E.2")*2 + Rules::getRule("CO.W.1");
                po->setX(poT->x() - (contactWidth - Rules::getRule("PO.W.1a"))/2);
            }
        }
    }
}

void Routing1::solvePolyDesignRulesConflicts()
{
    sortByXPos(cell->poItems);

    foreach(Metal* po, *(cell->poItems))
    {
        if(po->porpouse == 4)
        {
            Metal *collidingPo = getCollidingMetal(po,cell->poItems,Rules::getRule("PO.S.1"));

            if(collidingPo && collidingPo->x() < po->x())
            {
                qreal conflict = Rules::getRule("PO.S.1") - (po->x() - (collidingPo->x() +  collidingPo->bottomRight.x()));
                qreal leftDx = translateMetal(collidingPo, cell->poItems, conflict, Rules::getRule("PO.S.1"), "LEFT");
                qreal remainingConflict = conflict - leftDx;

                if(remainingConflict > 0)
                {
                    //qreal rightDx = translateMetal(collidingPo,cell->poItems, remainingConflict, Rules::getRule("PO.S.1"), "RIGHT");
                    //remainingConflict = remainingConflict - rightDx;

                    //if(remainingConflict > 0)
                    //{
                    po->setX(po->x() + remainingConflict);

                    //Transistor* t = (Transistor*)(po->linkedMetal->first()->linkedTransistors->first());
                    //translateTransistors(t, remainingConflict);
                    //}
                }
            }
        }
        else if(po->porpouse == 3)
        {
            Metal *collidingPo = getCollidingMetal(po,cell->poItems,Rules::getRule("PO.S.1"));

            if(collidingPo && collidingPo->x() < po->x())
            {
                qreal conflict = Rules::getRule("PO.S.1") - (po->x() - (collidingPo->x() +  collidingPo->bottomRight.x()));

                Transistor* t = (Transistor*)(po->linkedTransistors->first());
                translateTransistors(t, conflict);
            }
        }
    }
}

void Routing1::solveDesignRulesConflicts()
{
    solvePolyDesignRulesConflicts();
}

void Routing1::insertGatePolyContact(Metal* po)
{
    Metal* gateM1 = po->linkedMetal->first();
    Transistor* t = ((Transistor*)po->linkedTransistors->first());
    Transistor* oppositeTransistor = getOppositeTransistor(t);

    Metal* poCo = new Metal();
    poCo->metalType = "PO";
    poCo->bottomRight.setX(Rules::getRule("CO.E.2")*2 + Rules::getRule("CO.W.1"));
    poCo->bottomRight.setY(Rules::getRule("CO.E.2")*2 + Rules::getRule("CO.W.1"));
    poCo->setX(po->x() - (poCo->bottomRight.x() - po->bottomRight.x())/2 );
    poCo->setY(gateM1->y() - (poCo->bottomRight.y() - gateM1->bottomRight.y())/2);
    poCo->linkedMetal->append(po);
    poCo->linkedMetal->append(gateM1);
    poCo->net = po->net;
    poCo->porpouse = 4;

    if(!oppositeTransistor || t->transistorType.compare("PMOS") == 0 || t->gateNetName.compare(oppositeTransistor->gateNetName) != 0)
        cell->poItems->append(poCo);
}

void Routing1::insertGatePolyContacts()
{
    foreach(Metal* po, *(cell->poItems))
    {
        if(po->porpouse == 3)
        {
            insertGatePolyContact(po);
        }
    }
}

void Routing1::reRoute()
{
    resetRouting();
    internRouting();
    routeBandToGate();
    bandRouting();
    insertM1ToContacts();
    insertDiffToContacts();
    routeGates();
}

QString Routing1::getLeftNet(Transistor* t)
{
    return cell->getLeftNet(t);
}

QString Routing1::getRightNet(Transistor* t)
{
    if(t->flipped)
        return t->sourceNetName;

    return t->drainNetName;
}

void Routing1::fillNonGapSpaceWithDiff(Transistor* left, Transistor* right)
{
    Transistor* smaller = left->gateRect.height() < right->gateRect.height() ? left : right;

    Metal* diff = new Metal();
    diff->metalType = "OD";
    diff->net = getRightNet(left);
    diff->bottomRight = QPointF(right->x() - left->x(), smaller->w);
    diff->setPos(left->x(), smaller->y() + Rules::getRule("PO.O.1"));

    cell->diffItems->append(diff);
}

void Routing1::fillNonGapSpaceWithDiff(QList<Transistor*> *transistors)
{
    for(int i=0; i<transistors->size() - 1; i++)
    {
        Transistor* cur = transistors->at(i);
        Transistor* next = transistors->at(i+1);

        QString rightNet = getRightNet(cur);
        QString leftNet = getLeftNet(next);

        if(next->posIndex - cur->posIndex > 1 && rightNet.compare(leftNet) == 0)
            fillNonGapSpaceWithDiff(cur, next);
    }
}

void Routing1::fillNonGapSpaceWithDiff()
{
    fillNonGapSpaceWithDiff(cell->pTransistors);
    fillNonGapSpaceWithDiff(cell->nTransistors);
}

QList<Metal*> *Routing1::replaceMetal2WithMetal1(Metal *m2, Metal *m1)
{
    qreal x0PmosContact = m2->linkedMetal->first()->linkedMetal->first()->x();
    qreal x1PmosContact = m2->linkedMetal->first()->linkedMetal->last()->x();
    qreal middleTop = (x0PmosContact + x1PmosContact)/2;

    qreal x0NmosContact = m2->linkedMetal->last()->linkedMetal->first()->x();
    qreal x1NmosContact = m2->linkedMetal->last()->linkedMetal->last()->x();
    qreal middleBottom = (x0NmosContact + x1NmosContact)/2;

    Metal* m1Top = new Metal();
    Metal* m1Bottom = new Metal();

    m1Top->copy(m1);
    m1Bottom->copy(m1);

    qreal topWidth = qAbs(middleTop - m1->x());
    qreal bottomWidth = qAbs(middleBottom - m1->x());

    if(m1->x() < x0PmosContact)
        topWidth = x0PmosContact - m1->x();
    else if(m1->x() > x1PmosContact)
        topWidth =  m1->x() - x1PmosContact;

    if(m1->x() < x0NmosContact)
        bottomWidth = x0NmosContact - m1->x();
    else if(m1->x() > x1NmosContact)
        bottomWidth =  m1->x() - x1NmosContact;

    m1Top->setPos(m1->x() < middleTop ? m1->x() : middleTop, m2->y());

    m1Top->bottomRight = QPointF(topWidth, Rules::getRule("M1.W.1"));
    m1Bottom->bottomRight = QPointF(bottomWidth, Rules::getRule("M1.W.1"));

    m1Bottom->setPos(m1->x() < middleBottom ? m1->x() : middleBottom, m2->y() + m2->bottomRight.y() - Rules::getRule("M1.W.1"));

    if(getCollidingMetal(m1,cell->m1Items,Rules::getRule("M1.S.1"))     ||
       getCollidingMetal(m1Top,cell->m1Items,Rules::getRule("M1.S.1"))  ||
       getCollidingMetal(m1Bottom,cell->m1Items,Rules::getRule("M1.S.1")))
        return 0;

    QList<Metal*> *m1List = new QList<Metal*>();

    m1List->append(m1); m1List->append(m1Top); m1List->append(m1Bottom);

    return m1List;
}

void Routing1::replaceMetal2WithMetal1(Metal *m2)
{
    Metal* m1Left = new Metal();
    Metal* m1Right = new Metal();

    qreal x0PmosContact = m2->linkedMetal->first()->linkedMetal->first()->x();
    qreal x1PmosContact = m2->linkedMetal->first()->linkedMetal->last()->x();
    qreal middleTop = (x0PmosContact + x1PmosContact)/2;

    qreal x0NmosContact = m2->linkedMetal->last()->linkedMetal->first()->x();
    qreal x1NmosContact = m2->linkedMetal->last()->linkedMetal->last()->x();
    qreal middleBottom = (x0NmosContact + x1NmosContact)/2;

    qreal middle = (middleTop + middleBottom)/2;

    m1Left->copy(m2);
    m1Right->copy(m2);
    m1Left->setX(middle);
    m1Right->setX(middle);

    m1Left->metalType = m1Right->metalType = "M1";

    m1Left->bottomRight.setX(Rules::getRule("M1.W.1"));
    m1Right->bottomRight.setX(Rules::getRule("M1.W.1"));

    fixMetalPosition(m1Left,cell->m1Items,Rules::getRule("M1.S.1"),"LEFT");
    fixMetalPosition(m1Right,cell->m1Items,Rules::getRule("M1.S.1"),"RIGHT");

    QList<Metal*> *leftRouting = replaceMetal2WithMetal1(m2,m1Left);
    QList<Metal*> *rightRouting = replaceMetal2WithMetal1(m2,m1Right);
    QList<Metal*> *toBeInserted = 0;

    if(!leftRouting && rightRouting)
        toBeInserted = rightRouting;
    else if(!rightRouting && leftRouting)
        toBeInserted = leftRouting;
    else if(leftRouting && rightRouting)
    {
        if(m2->x() - m1Left->x() < m1Right->x() - m2->x())
            toBeInserted = leftRouting;
        else
            toBeInserted = rightRouting;
    }

    if(toBeInserted)
    {
        Metal* pM1 = m2->linkedMetal->first();
        Metal* nM1 = m2->linkedMetal->last();

        pM1->setX(pM1->linkedMetal->first()->x() - Rules::getRule("M1.E.1"));
        nM1->setX(nM1->linkedMetal->first()->x() - Rules::getRule("M1.E.1"));

        pM1->bottomRight.setX(pM1->linkedMetal->last()->x() -  pM1->linkedMetal->first()->x() + Rules::getRule("CO.W.1") + Rules::getRule("M1.E.1")*2 );
        nM1->bottomRight.setX(nM1->linkedMetal->last()->x() -  nM1->linkedMetal->first()->x() + Rules::getRule("CO.W.1") + Rules::getRule("M1.E.1")*2 );

        cell->m1Items->append(*toBeInserted);
        cell->m2Items->removeOne(m2);

        releaseMemory(m2);

        if(toBeInserted == leftRouting)
            releaseMemory(rightRouting);
        else
            releaseMemory(leftRouting);
    }
    else
    {
        releaseMemory(leftRouting);
        releaseMemory(rightRouting);
    }
}

void Routing1::replaceMetal2WithMetal1()
{
    foreach(Metal* m2, *(cell->m2Items))
        replaceMetal2WithMetal1(m2);
}

void Routing1::fixMetal2Height(Metal *m2)
{
    Metal* gateM1 = getGateM1(m2->net, cell->m1Items);

    if(!gateM1)
        return;

    if(m2->band.compare("NMOS") == 0)
    {
        m2->bottomRight.setY(m2->y() + m2->bottomRight.y() - gateM1->y() );
        m2->setY(gateM1->y());
    }
    else if(m2->band.compare("PMOS") == 0)
    {
        m2->bottomRight.setY(gateM1->y() - m2->y() + Rules::getRule("M1.W.1"));
    }
}

void Routing1::fixMetal2Height()
{
    foreach(Metal* m2, *(cell->m2Items))
        fixMetal2Height(m2);
}

void Routing1::insertDiffToContacts()
{
    foreach(Metal* co, *(cell->coItems))
    {
        if(co->net.compare("vcc") == 0 || co->net.compare("gnd") == 0)
            continue;

        Metal* diff = new Metal();
        diff->net = co->net;
        diff->metalType = "OD";
        diff->bottomRight.setX(Rules::getRule("CO.W.1") + Rules::getRule("CO.E.1")*2);

        qreal h, y;
        Transistor *t;

        if(co->band.compare("PMOS") == 0)
        {
            t = cell->pTransistors->first();
            h = co->y() - t->y() - Rules::getRule("PO.O.1") + Rules::getRule("CO.W.1") + Rules::getRule("CO.E.1");
            y = t->y() + Rules::getRule("PO.O.1");
        }
        else
        {
            t = cell->nTransistors->first();
            h = t->y() + t->gateRect.height() - co->y() - Rules::getRule("PO.O.1") + Rules::getRule("CO.E.1");
            y = co->y() - Rules::getRule("CO.E.1");
        }

        diff->bottomRight.setY(h);
        diff->setPos(co->x() - Rules::getRule("CO.E.1"), y);
        cell->diffItems->append(diff);
    }
}

void Routing1::routeBandToGate()
{
    routeBandToGate(cell->pTransistors);
    routeBandToGate(cell->nTransistors);
}

void Routing1::routeBandToGate(QList<Transistor*> *transistors)
{
    QStringList *diffToGateNets = getDiffToGateNets(transistors);
    sortByWidth(diffToGateNets);
    routeBandToGate(diffToGateNets, transistors);

    delete diffToGateNets;
}

void Routing1::routeBandToGate(QString net, QList<Transistor*> *transistors)
{
    QList<Metal*>* contacts = insertContacts(net,transistors);

    foreach(Metal* co, *(contacts))
    {
        QList<Metal*>* cur = new QList<Metal*>();

        cur->append(co);

        Metal *m1;
        Metal *m2 = new Metal();

        m2->metalType = "M2";
        m2->net = net;

        if(transistors->first()->transistorType.compare("PMOS") == 0)
        {
            m1 = insertHorizontalM1(cur,0, "DOWN");
            m2->bottomRight = QPointF(Rules::getRule("M2.W.1"), cell->gndRectItem->y() -  m1->y());
            m2->setX(m1->x() -(m2->bottomRight.x() - m1->bottomRight.x())/2);
            m2->setY(m1->y());
        }
        else
        {
            m1 = insertHorizontalM1(cur,cell->gndRectItem->y(), "UP");
            m2->bottomRight = QPointF(Rules::getRule("M2.W.1"), m1->y() + m1->bottomRight.y());
            m2->setX(m1->x() -(m2->bottomRight.x() - m1->bottomRight.x())/2);
            m2->setY(0);
        }

        m2->band = transistors->first()->transistorType;

        fixContactsPosition(cur,m1);

        m1->linkedMetal->append(co);
        m2->linkedMetal->append(m1);

        cell->m2Items->append(m2);
        cell->coItems->append(co);
        cell->m1Items->append(m1);

        delete cur;
    }
    delete contacts;
}

void Routing1::routeBandToGate(QStringList *bandToGateNets, QList<Transistor*> *transistors)
{
    foreach(QString net, *(bandToGateNets))
        routeBandToGate(net, transistors);
}

QStringList* Routing1::getDiffToGateNets(QList<Transistor*> *transistors)
{
    QStringList *diffToGateNets = new QStringList();
    QStringList *gateNets = cell->getGateNets();

    foreach(Transistor *t, *(transistors))
    {
        if(gateNets->contains(t->sourceNetName))
            diffToGateNets->append(t->sourceNetName);

        if(gateNets->contains(t->drainNetName))
            diffToGateNets->append(t->drainNetName);
    }

    diffToGateNets->removeDuplicates();

    delete gateNets;
    return diffToGateNets;
}

void Routing1::routeVccGnd()
{
    routeVccGnd("vcc", cell->pTransistors);
    routeVccGnd("gnd", cell->nTransistors);
}

Transistor* Routing1::getGreaterTransistor(QString net, Transistor* t, QList<Transistor*> *transistors)
{
    Transistor* prev = cell->getTransistorByPosIndex(transistors, t->posIndex -1);
    Transistor* next = cell->getTransistorByPosIndex(transistors, t->posIndex + 1);

    if(t->sourceNetName.compare(net) == 0)
    {
        if(!t->flipped && prev && prev->gateRect.height() > t->gateRect.height())
            return prev;
        else if(next && next->gateRect.height() > t->gateRect.height())
            return next;
    }
    else
    {
        if(!t->flipped && next && next->gateRect.height() > t->gateRect.height())
            return next;
        else if(prev && prev->gateRect.height() > t->gateRect.height())
            return prev;
    }

    return t;
}

void Routing1::routeVccGnd(QString net, QList<Transistor*> *transistors)
{
    foreach(Transistor *t, *(transistors))
    {
        qreal x = getContactPosition(net, transistors, t);

        if(x)
        {
            Metal* co = new Metal();
            co->net = net;
            co->metalType = "CO";
            co->bottomRight = QPointF(Rules::getRule("CO.W.1"), Rules::getRule("CO.W.1"));
            co->setX(x - Rules::getRule("CO.W.1")/2);

            Metal* m1 = new Metal();
            m1->net = net;
            m1->metalType = "M1";
            m1->bottomRight.setX(Rules::getRule("CO.W.1") + Rules::getRule("M1.E.1")*2);
            m1->bottomRight.setY(co->y()  + Rules::getRule("CO.W.1") + Rules::getRule("M1.E.1"));
            m1->setX(co->x() - Rules::getRule("M1.E.1"));

            Metal* diff = new Metal();
            diff->net = co->net;
            diff->metalType = "OD";
            diff->bottomRight.setX(Rules::getRule("CO.W.1") + Rules::getRule("CO.E.1")*2);
            diff->bottomRight.setY(Rules::getRule("CO.W.1") + Rules::getRule("CO.E.1")*2);

            Transistor *gt = getGreaterTransistor(net, t, transistors);

            if(t->transistorType.compare("NMOS") == 0)
            {
                m1->bottomRight.setY(cell->gndRectItem->y() - gt->y() - Rules::getRule("PO.O.1") + cell->gndHeight);
                m1->setY(gt->y() + Rules::getRule("PO.O.1"));
                cutCollidingArea(m1,"DOWN");
                co->setY(m1->y() + Rules::getRule("M1.E.1"));

                diff->setPos(co->x() - Rules::getRule("CO.E.1"), co->y() - Rules::getRule("CO.E.1"));

                qreal transistorDiffYPos = t->y() + t->gateRect.height() - Rules::getRule("PO.O.1");
                if(diff->y() > transistorDiffYPos)
                {
                    diff->bottomRight.setY(diff->bottomRight.y() + diff->y() - transistorDiffYPos );
                    diff->setY(transistorDiffYPos);
                }

                if(m1->bottomRight.y() > cell->gndHeight)
                    cell->m1Items->append(m1);
            }
            else
            {
                m1->bottomRight.setY(gt->y() + gt->gateRect.height() - Rules::getRule("PO.O.1"));
                m1->setY(0);
                cutCollidingArea(m1,"UP");
                m1->setY(0);
                co->setY(m1->y() +  m1->bottomRight.y() - Rules::getRule("M1.E.1") - Rules::getRule("CO.W.1"));

                diff->setPos(co->x() - Rules::getRule("CO.E.1"), co->y() - Rules::getRule("CO.E.1"));

                qreal transistorDiffYPos = t->y() + Rules::getRule("PO.O.1");
                if(diff->y() + diff->bottomRight.y() < transistorDiffYPos)
                    diff->bottomRight.setY(transistorDiffYPos - diff->y());

                if(m1->bottomRight.y() > cell->vccHeight)
                    cell->m1Items->append(m1);
            }



            cell->coItems->append(co);
            cell->diffItems->append(diff);
        }
    }
}

void Routing1::insertM1ToContacts()
{
    foreach(Metal* co, *(cell->coItems))
    {
        if(co->net.compare("vcc") == 0 || co->net.compare("gnd") == 0)
            continue;

        Metal* m1 = new Metal();
        m1->net = co->net;
        m1->bottomRight.setX(Rules::getRule("CO.W.1") + Rules::getRule("M1.E.1")*2);
        m1->bottomRight.setY(m1->bottomRight.x());

        m1->setPos(co->x() - Rules::getRule("M1.E.1"), co->y() - Rules::getRule("M1.E.1"));

        stretchM1(m1, co);
        cell->m1Items->append(m1);
    }
}

void Routing1::stretchM1(Metal* m1, Metal* co)
{
    if(co->band.compare("PMOS") == 0)
    {
        Transistor *t = cell->pTransistors->first();
        qreal h = m1->y() - t->y() + m1->bottomRight.y() - Rules::getRule("PO.O.1") -(m1->bottomRight.y() - Rules::getRule("M1.W.1"))/2;

        m1->bottomRight.setY(h);
        m1->setY(t->y() + Rules::getRule("PO.O.1"));

        cutCollidingArea(m1, "DOWN");

        if(m1->bottomRight.y() < Rules::getRule("M1.E.1")*2 + Rules::getRule("CO.W.1") )
            m1->bottomRight.setY(Rules::getRule("M1.E.1")*2 + Rules::getRule("CO.W.1"));

        co->setY(m1->y() + Rules::getRule("M1.E.1"));
    }
    else
    {
        qreal h = cell->gndRectItem->y() - m1->y();

        m1->setY(m1->y() + (m1->bottomRight.y() - Rules::getRule("M1.W.1"))/2);
        m1->bottomRight.setY(h);
        cutCollidingArea(m1, "UP");

        if(m1->bottomRight.y() < Rules::getRule("M1.E.1")*2 + Rules::getRule("CO.W.1") )
        {
            m1->bottomRight.setY(Rules::getRule("M1.E.1")*2 + Rules::getRule("CO.W.1"));
            m1->setY(m1->y() - (m1->bottomRight.y() - Rules::getRule("M1.W.1"))/2);
        }

        co->setY(m1->y() + m1->bottomRight.y() - Rules::getRule("M1.E.1") - Rules::getRule("CO.W.1"));
    }
}
void Routing1::cutCollidingArea(Metal* m1, QString direction)
{
    while(true)
    {
        Metal *collidingM1 = getCollidingMetal(m1,cell->m1Items,Rules::getRule("M1.S.1"));
        if(collidingM1)
        {
            if(direction.compare("DOWN") == 0)
            {
                qreal newY = collidingM1->y() + collidingM1->bottomRight.y() + Rules::getRule("M1.S.1");
                m1->bottomRight.setY(m1->y() + m1->bottomRight.y() - newY);
                m1->setY(newY);
            }
            else
            {
                m1->bottomRight.setY(collidingM1->y() - m1->y() - Rules::getRule("M1.S.1"));
            }
        }
        else
            break;
    }
}

void Routing1::bandRouting()
{
    QStringList *interBandNets = getInterBandNets();
    sortByWidth(interBandNets);
    routeBandNets(interBandNets);

    delete interBandNets;
}

void Routing1::routeBandNets(QStringList *interBandNets)
{
    foreach(QString net, *(interBandNets))
        routeBandNet(net);
}

void Routing1::routeBandNet(QString net)
{
    qreal x0p  = getFirstXOcurrency(net, cell->pTransistors, true, false);
    qreal x1p  = getLastXOcurrency(net, cell->pTransistors, true, false);

    qreal x0n  = getFirstXOcurrency(net, cell->nTransistors, true, false);
    qreal x1n  = getLastXOcurrency(net, cell->nTransistors, true, false);

    qreal minX = x0p < x0n ? x0p : x0n;
    qreal maxX = x1p > x1n ? x1p : x1n;
    qreal middle = (minX + maxX) /2;

    Metal* m2Left = insertVerticalM2(net, middle, "LEFT");
    Metal* m2Right = insertVerticalM2(net, middle, "RIGHT");

    qreal leftDistance = middle - (m2Left->x() + m2Left->bottomRight.x());
    qreal rightDistance = m2Right->x() - middle;

    Metal* m2;
    if(leftDistance < rightDistance)
    {
        releaseMemory(m2Right);
        m2 = m2Left;
    }
    else
    {
        releaseMemory(m2Left);
        m2 = m2Right;
    }

    Metal *pM1 = insertHorizontalM1(m2, cell->pTransistors);
    Metal *nM1 = insertHorizontalM1(m2, cell->nTransistors);

    m2->bottomRight.setY(nM1->y() - pM1->y() + Rules::getRule("M1.W.1"));
    m2->setY(pM1->y());
    m2->linkedMetal->append(pM1);
    m2->linkedMetal->append(nM1);

    cell->m2Items->append(m2);
    cell->m1Items->append(pM1);
    cell->m1Items->append(nM1);
}

Metal* Routing1::insertVerticalM2(QString net, qreal middle, QString direction)
{
    Metal *m2 = new Metal();

    m2->bottomRight = QPointF(Rules::getRule("M2.W.1"), cell->gndRectItem->y());
    m2->metalType = "M2";
    m2->net = net;
    m2->setPos(middle - Rules::getRule("M2.W.1")/2,0);

    while(true)
    {
        Metal *collidingM2 = getCollidingMetal(m2,cell->m2Items,Rules::getRule("M2.S.1"));

        if(collidingM2)
        {
            if(direction.compare("RIGHT") == 0)
                m2->setX(collidingM2->x() + collidingM2->bottomRight.x() + Rules::getRule("M2.S.1"));
            else
                m2->setX(collidingM2->x() - m2->bottomRight.x() -Rules::getRule("M2.S.1"));
        }
        else
            break;
    }
    return m2;
}

Metal* Routing1::insertHorizontalM1(Metal* m2, QList<Transistor*> *transistors)
{
    QList<Metal*> *contacts = insertContacts(m2->net,transistors);

    foreach(Metal* co, *(contacts))
        cell->coItems->append(co);

    Metal *tempMetal2Contact = createContact(m2);
    contacts->append(tempMetal2Contact);

    sortByXPos(contacts);

    QString direction = "DOWN";
    qreal initialY = 0;

    if(transistors->first()->transistorType.compare("NMOS") == 0)
    {
        direction = "UP";
        initialY = cell->gndRectItem->y();
    }

    Metal* m1 = insertHorizontalM1(contacts,initialY, direction);
    m1->linkedMetal->removeOne(tempMetal2Contact);

    fixContactsPosition(contacts,m1);
    m1->bottomRight.setY(Rules::getRule("M1.W.1"));
    m1->setY(m1->y() + (Rules::getRule("CO.W.1") + Rules::getRule("M1.E.1")*2 - Rules::getRule("M1.W.1"))/2);
    return m1;
}

bool lessThanX(Metal* m1, Metal* m2)
{
    return m1->x() < m2->x();
}
bool lessThanY(Metal* m1, Metal* m2)
{
    return m1->y() < m2->y();
}

void Routing1::sortByXPos(QList<Metal*> *m)
{
    qSort(m->begin(), m->end(), lessThanX);
}

void Routing1::sortByYPos(QList<Metal*> *m)
{
    qSort(m->begin(), m->end(), lessThanY);
}

Metal* Routing1::createContact(Metal* m)
{
    Metal* co = new Metal();

    co->net = m->net;
    co->metalType = "CO";
    co->bottomRight = QPointF(Rules::getRule("CO.W.1"), Rules::getRule("CO.W.1"));

    co->setX(m->x());

    return co;
}

QStringList* Routing1::getInterBandNets()
{
    QStringList *interBandNets = new QStringList();

    foreach(Transistor *t, *(cell->pTransistors))
    {
        if(isInterBandNet(t->sourceNetName))
            interBandNets->append(t->sourceNetName);

        if(isInterBandNet(t->drainNetName))
            interBandNets->append(t->drainNetName);
    }

    interBandNets->removeDuplicates();

    return interBandNets;
}
bool Routing1::isInterBandNet(QString net)
{
    QStringList* gateNets = cell->getGateNets();

    bool ret = false;

    if(!(net.compare("vcc") == 0 ||
             net.compare("gnd") == 0 ||
             gateNets->contains(net)  ||
             isInternNet(net, cell->nTransistors)||
             isInternNet(net, cell->pTransistors)))
        ret = true;

    delete gateNets;
    return ret;
}

Transistor* Routing1::getOppositeTransistor(Transistor* t)
{
    QList<Transistor*> *transistors = cell->pTransistors;

    if(t->transistorType.compare("PMOS") == 0)
        transistors = cell->nTransistors;

    return cell->getTransistorByPosIndex(transistors, t->posIndex);
}

QStringList* Routing1::getOppositeGateNets(QString gateNet, QList<Transistor*> *transistors)
{
    QStringList* conflicts = new QStringList();

    foreach(Transistor *t, *(transistors))
    {
        if(t->gateNetName.compare(gateNet) == 0)
        {
            Transistor* opposite = getOppositeTransistor(t);

            if(opposite && opposite->gateNetName.compare(gateNet) != 0)
                conflicts->append(opposite->gateNetName);
        }
    }
    return conflicts;
}

QStringList* Routing1::getOppositeGateNets(QString gateNet)
{
    QStringList* conflicts = getOppositeGateNets(gateNet, cell->nTransistors);

    QStringList* pmosConflicts = getOppositeGateNets(gateNet, cell->pTransistors);
    conflicts->append(*pmosConflicts);

    delete pmosConflicts;
    return conflicts;
}

bool Routing1::hasIntersection(QString gateNet1, QString gateNet2)
{
    qreal x0_gateNet1 = getFirstXOcurrency(gateNet1,false, true);
    qreal x1_gateNet1 = getLastXOcurrency(gateNet1,false, true);

    qreal x0_gateNet2 = getFirstXOcurrency(gateNet2,false, true);
    qreal x1_gateNet2 = getLastXOcurrency(gateNet2,false, true);

    return ( (x0_gateNet1 >= x0_gateNet2 && x0_gateNet1 <= x1_gateNet2 ) ||
             (x1_gateNet1 >= x0_gateNet2 && x1_gateNet1 <= x1_gateNet2 ) );
}

QStringList* Routing1::getGatesM1Conflicts(QString gateNet)
{
    QStringList* gateNets = cell->getGateNets();
    QStringList* conflicts = new QStringList();

    foreach(QString curNet, *(gateNets))
        if(curNet.compare(gateNet) != 0 && hasIntersection(curNet, gateNet))
            conflicts->append(curNet);

    delete gateNets;
    return conflicts;
}

QStringList* Routing1::getGateConflicts(QString gateNet)
{
    QStringList* conflicts = getOppositeGateNets(gateNet);

    QStringList* gatesM1Conflicts = getGatesM1Conflicts(gateNet);
    conflicts->append(*gatesM1Conflicts);

    delete gatesM1Conflicts;
    return conflicts;
}

QList<QStringList*>* Routing1::getGateConflicts(QStringList* gateNets)
{
    QList<QStringList*>* conflicts = new QList<QStringList*>();

    foreach(QString net, *(gateNets))
    {
        QStringList* gateConflicts = getGateConflicts(net);
        conflicts->append(gateConflicts);
    }

    return conflicts;
}

QList<Metal*>* Routing1::insertGateContacts(QString gateNet, QList<Transistor*> *transistors)
{
    QList<Metal*> *contacts = new QList<Metal*>();

    foreach(Transistor *t, *(transistors))
    {
        if(t->gateNetName.compare(gateNet) == 0)
        {
            Transistor* oppositeTransistor = getOppositeTransistor(t);

            if(!oppositeTransistor || oppositeTransistor->gateNetName.compare(gateNet) != 0)
            {
                contacts->append(createPoContact(t));
            }
            else if(oppositeTransistor &&
                    oppositeTransistor->gateNetName.compare(gateNet) == 0 &&
                    t->transistorType.compare("PMOS") == 0)
            {
                contacts->append(createPoContact(t));
            }
        }
    }
    return contacts;
}

QList<Metal*>* Routing1::insertGateContacts(QString gateNet)
{
    QList<Metal*> *contacts = new QList<Metal*>();

    QList<Metal*> *pDiffContacts = insertContacts(gateNet, cell->pTransistors);
    QList<Metal*> *nDiffContacts = insertContacts(gateNet, cell->nTransistors);
    QList<Metal*> *pGatesContacts = insertGateContacts(gateNet, cell->pTransistors);
    QList<Metal*> *nGatesContacts = insertGateContacts(gateNet, cell->nTransistors);

    contacts->append(*nDiffContacts);
    contacts->append(*pDiffContacts);
    contacts->append(*pGatesContacts);
    contacts->append(*nGatesContacts);

    sortByXPos(contacts);

    delete pGatesContacts;
    delete nGatesContacts;
    delete pDiffContacts;
    delete nDiffContacts;

    return contacts;
}

Metal* Routing1::getMetalNet(QString net, QList<Metal*>* metalItems)
{
    foreach(Metal* m, *(metalItems))
        if(m->net.compare(net) == 0)
            return m;

    return 0;
}

bool Routing1::hasOppositeGateConflict(Transistor *t, QList<Metal*>* m1Items)
{
    Transistor* pt, *nt;

    if(t->transistorType.compare("PMOS") == 0){
        pt = t; nt = getOppositeTransistor(t);
    }
    else{
        nt = t; pt = getOppositeTransistor(t);
    }

    if(!pt || !nt || pt->gateNetName.compare(nt->gateNetName) == 0 )
        return false;

    Metal* ptMetalNet = getGateM1(pt->gateNetName, m1Items);
    Metal* ntMetalNet = getGateM1(nt->gateNetName, m1Items);

    if(!ptMetalNet || !ntMetalNet)
        return false;

    if(ntMetalNet->y() < pt->y() + pt->gateRect.height() + Rules::getRule("PO.S.1"))
        return true;

    if(ptMetalNet->y() > nt->y() - Rules::getRule("PO.S.1"))
        return true;

    return (ptMetalNet->y() > ntMetalNet->y());
}

bool Routing1::hasSelfGateConflict(Transistor *t, QList<Metal*>* m1Items)
{
    Metal* tMetalNet = getMetalNet(t->gateNetName, m1Items);

    if(!tMetalNet)
        return false;

    if(t->transistorType.compare("PMOS") == 0 && tMetalNet->y() < t->y() + t->gateRect.height())
        return true;
    else if(t->transistorType.compare("NMOS") == 0 && tMetalNet->y() > t->y())
        return true;

    return false;
}

int Routing1::countUnsolvedConflicts(QList<Metal*>* m1Items, QList<Transistor*> *transistors)
{
    int count = 0;

    foreach(Transistor *t, *(transistors))
    {
        int curCount = count;

        if(hasOppositeGateConflict(t, m1Items) && t->transistorType.compare("PMOS") == 0)
            count++;

        if(hasSelfGateConflict(t, m1Items))
            count++;

        if(count - curCount == 2)
            count += 100;
    }

    return count;
}

int Routing1::countOutsideM1(QList<Metal*>* m1Items)
{
    int count = 0;

    foreach(Metal* m, *(m1Items))
        if(m->y() > cell->gndRectItem->y())
            count+=1;

    return count;
}

int Routing1::countUnsolvedConflicts(QList<Metal*>* m1Items)
{
    return countUnsolvedConflicts(m1Items, cell->pTransistors) +
           countUnsolvedConflicts(m1Items, cell->nTransistors)
           + countOutsideM1(m1Items)*100;
}

qreal Routing1::getMinSelfGateConflict(Metal* m1, qreal d)
{
    qreal minConflict = 1e6;
    qreal poContactWidth = Rules::getRule("CO.E.2")*2 + Rules::getRule("CO.W.1");
    qreal m1OffsetOfPoContact = (poContactWidth - Rules::getRule("M1.W.1"))/2;

    foreach(Transistor* pt, *(cell->pTransistors))
    {
        qreal ptGateYPos = pt->y() + pt->gateRect.height();
        qreal rightM1Position = ptGateYPos - Rules::getRule("PO.O.1") + Rules::getRule("PO.C.1") + m1OffsetOfPoContact;

        if(pt->gateNetName.compare(m1->net) == 0 && rightM1Position >= m1->y())
        {
            qreal curConflict = rightM1Position - m1->y();

            if(curConflict < minConflict && curConflict > d)
                minConflict = curConflict;
        }
    }
    if(minConflict == 1e6)
        return 0;

    return minConflict;
}

QList<Metal*>* Routing1::getHigherMetals(Metal* m1, QList<Metal*>* m1Items)
{
    QList<Metal*>* higherMetals = new QList<Metal*>();

    foreach(Metal* m, *(m1Items))
        if(m != m1 && m->y() <= m1->y())
            higherMetals->append(m);

    return higherMetals;
}

void Routing1::translateGateM1(Metal* m1, QList<Metal*>* m1Items, qreal d)
{
    m1->bottomRight.setY(m1->bottomRight.y() + d);

    foreach(Metal* m, *(m1Items))
    {
        if(m != m1)
        {
            QList<Metal*>* higherMetals = getHigherMetals(m, m1Items);

            fixMetalPosition(m, higherMetals,Rules::getRule("M1.S.1"),"DOWN");
            fixMetalPosition(m, cell->m1Items,Rules::getRule("M1.S.1"),"DOWN");

            delete higherMetals;
        }
    }

    m1->setY(m1->y() + d);
    m1->bottomRight.setY(Rules::getRule("M1.W.1"));
}

void Routing1::fitToBestPlace(QList<Metal*>* m1Items)
{
    sortByYPos(m1Items);
    int lastConflictsCount = countUnsolvedConflicts(m1Items);
    int index = 0;
    qreal d = -1;

    while(true)
    {
        if(index >= m1Items->size())
            break;

        Metal *m1 =  m1Items->at(index);
        d = getMinSelfGateConflict(m1, d);

        if(d == 0)
        {
            d = -1;
            index++;
            continue;
        }
        QList<qreal>* previousY = getYPositions(m1Items);
        translateGateM1(m1, m1Items, d);
        qreal curConflictsCount = countUnsolvedConflicts(m1Items);

        if(curConflictsCount > lastConflictsCount)
        {
            setYPosition(m1Items, previousY);
            continue;
        }
        lastConflictsCount = curConflictsCount;
    }
}
void Routing1::setYPosition(QList<Metal*>* m1Items, QList<qreal>* yPositions)
{
    int i=0;
    foreach(Metal *m, *(m1Items))
        m->setY(yPositions->at(i++));
}

QList<qreal>* Routing1::getYPositions(QList<Metal*>* m1Items)
{
    QList<qreal>* yPositions = new QList<qreal>();

    foreach(Metal *m, *(m1Items))
        yPositions->append(m->y());

    return yPositions;
}

QList<Metal*>* Routing1::insertM1GateItems(QStringList* solution, QStringList* gateNets)
{
    QList<Metal*>* m1Items = new QList<Metal*>();

    qreal lastY = 0;
    foreach(QString index, *(solution))
    {
        QList<Metal*> *contacts = insertGateContacts(gateNets->at(index.toInt()));

        Metal* m1 = insertHorizontalM1(contacts, lastY, "DOWN");

        lastY = m1->y();

        //fixContactsPosition(contacts, m1);

        m1->bottomRight.setY(Rules::getRule("M1.W.1"));
        m1->setY(m1->y() + (Rules::getRule("CO.W.1") + Rules::getRule("M1.E.1")*2 - Rules::getRule("M1.W.1"))/2);

        cell->m1Items->append(m1);

        m1Items->append(m1);

        releaseMemory(contacts);
    }

    foreach(Metal* m, *(m1Items))
        cell->m1Items->removeOne(m);

    return m1Items;
}

int Routing1::evaluateSolution(QStringList* solution, QStringList* gateNets)
{
    QList<Metal*>* m1Items = insertM1GateItems(solution,gateNets);

    fitToBestPlace(m1Items);

    int ret = countUnsolvedConflicts(m1Items);

    releaseMemory(m1Items);

    return ret;
}

bool Routing1::canSwap(QString net1, QString net2, QList<QStringList*>* conflicts, QStringList* gateNets)
{
    return conflicts->at(net1.toInt())->contains(gateNets->at(net2.toInt()));
}

QStringList* Routing1::getNextSolution(QStringList* curSolution, QList<QStringList*>* conflicts, QStringList* gateNets)
{
    QString smallest = "9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9";
    QString initial = curSolution->join(",");

    for(int i=0; i < curSolution->size(); i++)
    {
        for(int j=i+1; j < curSolution->size(); j++)
        {
            if(canSwap(curSolution->at(i), curSolution->at(j), conflicts, gateNets))
            {
                QStringList curList = *curSolution;
                curList.swap(i,j);

                QString cur = curList.join(",");

                if(cur.compare(smallest) < 0 && cur.compare(initial) > 0)
                    smallest = cur;
            }
        }
    }

    curSolution->clear();
    curSolution->append(smallest.split(","));

    if(smallest.compare("9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9") == 0)
        return 0;

    return curSolution;
}

void Routing1::routeGatesWithHorizontalM1()
{
    QStringList* gateNets = cell->getGateNets();
    QStringList* curSolution = new QStringList();
    QStringList* bestSolution = new QStringList();
    QList<QStringList*>* conflicts = getGateConflicts(gateNets);

    qreal bestScore = 1e5;

    for(int i=0; i<gateNets->size(); i++)
        curSolution->append(QString::number(i));

    while(true)
    {
        qreal curScore = evaluateSolution(curSolution, gateNets);

        if(curScore < bestScore)
        {
            bestScore = curScore;
            *bestSolution = *curSolution;
        }

        curSolution = getNextSolution(curSolution, conflicts, gateNets);

        if(!curSolution)
            break;
    }

    QList<Metal*>* m1Items = insertM1GateItems(bestSolution, gateNets);

    fitToBestPlace(m1Items);

    foreach(Metal* m ,*(m1Items))
    {
        m->gateM1 = true;
        cell->m1Items->append(m);
    }

    delete curSolution;
    delete gateNets;
    delete bestSolution;

    foreach(QStringList* list, *(conflicts))
        delete list;

    delete conflicts;
}

QStringList *Routing1::getDiffToGateNets()
{
    QStringList *diffToGateNets = getDiffToGateNets(cell->pTransistors);
    diffToGateNets->append(*(getDiffToGateNets(cell->nTransistors)));

    return diffToGateNets;
}

QList<Metal*>* Routing1::getGatesM1()
{
    QList<Metal*>* gatesM1 = new QList<Metal*>();

    foreach(Metal* m, *(cell->m1Items))
        if(m->gateM1)
            gatesM1->append(m);

    return gatesM1;
}

QList<Metal*>* Routing1::getGateContacts(Metal* m)
{
    return insertGateContacts(m->net);
}

bool Routing1::coverAtLeastOneTransistor(Metal* m, QList<Transistor*> *transistors)
{
    foreach(Transistor* t, *(transistors))
        if(m->x() <= t->x() && t->x() < m->x() + m->bottomRight.x() && t->gateNetName.compare(m->net) == 0 )
            return true;

    return false;
}

bool Routing1::coverBothBands(Metal* m)
{
    return (coverAtLeastOneTransistor(m, cell->pTransistors) && coverAtLeastOneTransistor(m, cell->nTransistors));
}

int Routing1::getFirstDiffContactIndex(QList<Metal*>* contacts)
{
    for(int i=0; i< contacts->size(); i++)
    {
        Metal* co = contacts->at(i);

        if(co->band.compare("NONE") != 0)
            return i;
    }

    return -1;
}

int Routing1::getLastDiffContactIndex(QList<Metal*>* contacts)
{
    for(int i=contacts->size() - 1; i >= 0 ; i--)
    {
        Metal* co = contacts->at(i);

        if(co->band.compare("NONE") != 0)
            return i;
    }

    return -1;
}

QList<Metal*>* Routing1::generatePossibleSolutionsForShorteningGateM1(Metal* m)
{
    QList<Metal*>* solutions = new QList<Metal*>();
    QList<Metal*>* contacts  = getGateContacts(m);

    int firstDiffContactIndex = getFirstDiffContactIndex(contacts);
    int lastDiffContactIndex  = getLastDiffContactIndex(contacts);

    int maxIndex = firstDiffContactIndex >= 0 ?  firstDiffContactIndex : contacts->size() - 1;

    for(int i=0; i <= maxIndex; i++)
    {
        int j = lastDiffContactIndex < i ? i : lastDiffContactIndex;

        for(; j<contacts->size(); j++)
        {
            Metal* newM1 = new Metal();
            newM1->copy(m);

            qreal x0 = contacts->at(i)->x();
            qreal x1 = contacts->at(j)->x() + Rules::getRule("CO.W.1");
            newM1->bottomRight.setX(x1 - x0);
            newM1->setPos(x0,m->y());

            if(coverBothBands(newM1))
                solutions->append(newM1);
            else
                releaseMemory(newM1);
        }
    }

    releaseMemory(contacts);
    return solutions;
}

void Routing1::pushM1GatesUp(QList<Metal*>* m1Items)
{
    qreal lastY = 0;

    foreach(Metal* m, *(m1Items))
    {
        m->setY(lastY);

        qreal contactSpacing = (Rules::getRule("M1.E.1")*2 + Rules::getRule("CO.W.1") - Rules::getRule("M1.W.1"))/2;

        fixMetalPosition(m,cell->m1Items,Rules::getRule("M1.S.1") ,"DOWN");
        fixMetalPosition(m,m1Items,Rules::getRule("M1.S.1") + contactSpacing,"DOWN");
        fixMetalPosition(m,cell->m1Items,Rules::getRule("M1.S.1") ,"DOWN");

        lastY = m->y();
    }
}

QList<QList<Metal*>*>* Routing1::getPossibleSolutionsForShorteningGateM1()
{
    QList<QList<Metal*>*>* solutions = new QList<QList<Metal*>*>();
    QList<Metal*>* gatesM1 = getGatesM1();

    pushM1GatesUp(gatesM1);

    foreach(Metal* m, *(gatesM1))
        solutions->append(generatePossibleSolutionsForShorteningGateM1(m));

    delete gatesM1;
    return solutions;
}

void Routing1::condenseGateM1(QList<Metal*>* m1Items)
{
    for(int i=0; i<m1Items->size() - 1; i++)
    {
        Metal* cur = m1Items->at(i);
        Metal* next = m1Items->at(i+1);

        qreal nextY = next->y();

        next->setY(cur->y());

        QList<Metal*>* nonGateM1 = getNonGateMetal(cell->m1Items);

        qreal contactSpacing = (Rules::getRule("M1.E.1")*2 + Rules::getRule("CO.W.1") - Rules::getRule("M1.W.1"))/2;

        fixMetalPosition(next,nonGateM1,Rules::getRule("M1.S.1"), "DOWN");
        fixMetalPosition(next,m1Items,Rules::getRule("M1.S.1") + contactSpacing, "DOWN");
        fixMetalPosition(next,nonGateM1,Rules::getRule("M1.S.1"), "DOWN");

        delete nonGateM1;

        if(next->y() > nextY)
            next->setY(nextY);
    }
}
QList<Metal*>* Routing1::getNonGateMetal(QList<Metal*> *items)
{
    QList<Metal*>* nonGateM1 = new QList<Metal*>();

    foreach(Metal* m, *items)
        if(m->gateM1 == false)
            nonGateM1->append(m);

    return nonGateM1;
}

QList<Metal*>* Routing1::createSolutionForShorteningGateM1(QList<int>* combination, QList<QList<Metal*>*> *possibleSolutions)
{
    QList<Metal*>* solution = new QList<Metal*>();

    for(int i=0; i<combination->size(); i++)
    {
        Metal* newM1 = new Metal();
        newM1->copy(possibleSolutions->at(i)->at(combination->at(i)));
        solution->append(newM1);
    }

    condenseGateM1(solution);
    return solution;
}

bool Routing1::isLastCombination(QList<int>* curCombination, QList<QList<Metal*>*> *possibleSolutions)
{
    for(int i=0; i<curCombination->size(); i++)
    {
        int value = curCombination->at(i);

        if(value != possibleSolutions->at(i)->size() -1)
            return false;
    }

    return true;
}

void Routing1::getNextCombination(QList<int>* curCombination, QList<QList<Metal*>*> *possibleSolutions)
{
    for(int i=0; i<curCombination->size(); i++)
    {
        int newValue = curCombination->at(i) + 1;

        if(newValue >= possibleSolutions->at(i)->size())
            curCombination->replace(i, 0);
        else
        {
            curCombination->replace(i, newValue);
            break;
        }
    }
}

int Routing1::countVerticalGateConflicts(QList<Metal*>* polyItems)
{
    int count = 0;

    foreach(Metal *po, *(polyItems))
        count += getCollidingMetal(po,polyItems,Rules::getRule("PO.S.1")) == 0 ? 0 : 1;

    return count;
}

int Routing1::countOutsideMetal(QList<Metal*>* items)
{
    int count = 0;

    foreach(Metal* m, *(items))
        if(m->y() < 0 || m->y() > cell->gndRectItem->y() + cell->gndHeight)
            count++;

    return count;
}

int Routing1::countHorizontalPolyItems(QList<Metal*>* poItems)
{
    int count = 0;

    foreach(Metal* po, *(poItems))
        if(po->bottomRight.y() <= Rules::getRule("PO.W.1a") + 0.0001)
            count++;

    return count;
}

int Routing1::evaluateSolutionForShoteningGateM1(QList<Metal*>* solution, QList<Metal*>* polyItems)
{
    int vgcW = 3;
    int omW = 6;
    int hpoW = 1;

    int score = countVerticalGateConflicts(polyItems)*vgcW;
    score += countOutsideMetal(polyItems)*omW;
    score += countHorizontalPolyItems(polyItems)*hpoW;

    return score;
}

QList<Metal*>* Routing1::createPolySideConnections(QList<Transistor*> *transistors)
{
    QList<Metal*>* poItems = new QList<Metal*>();

    QList<Metal*>* transistorsPoItems = getTransistorPoItems();

    qreal initialY = transistors->first()->y() + Rules::getRule("PO.O.1") - Rules::getRule("PO.C.1");
    QString direction = "UP";

    if(transistors->first()->transistorType.compare("NMOS") == 0)
    {
        direction = "DOWN";
        initialY = transistors->first()->y() + transistors->first()->gateRect.height() - Rules::getRule("PO.O.1") + Rules::getRule("PO.C.1");
    }

    foreach(Transistor* t, *(transistors))
    {
        if(t->routed == false)
        {
            Transistor* sibling = getLessBlockingClosestSibling(t);

            Transistor *left  = sibling->x() < t->x() ? sibling : t;
            Transistor *right = sibling->x() > t->x() ? sibling : t;

            Metal* po = insertHorizontalPoly(left, right,cell->poItems,initialY,direction);
            po->band = left->transistorType;
            po->linkedTransistors->append((void*)(left));
            po->linkedTransistors->append((void*)(right));

            fixMetalPosition(po, cell->diffItems, Rules::getRule("PO.C.1"), direction);
            fixMetalPosition(po,transistorsPoItems,Rules::getRule("PO.S.1"), direction);

            poItems->append(po);
        }
    }

    releaseMemory(transistorsPoItems);

    return poItems;
}

QList<Metal*>* Routing1::createPolySideConnections()
{
    QList<Metal*>* poItems = new QList<Metal*>();

    QList<Metal*>* pmosPolySideConnections = createPolySideConnections(cell->pTransistors);
    sortByLessBlockingShorterPoly(pmosPolySideConnections);
    fixHorizontalGatePoPosition(pmosPolySideConnections);

    QList<Metal*>* nmosPolySideConnections = createPolySideConnections(cell->nTransistors);
    sortByLessBlockingShorterPoly(nmosPolySideConnections);
    fixHorizontalGatePoPosition(nmosPolySideConnections);

    poItems->append(*pmosPolySideConnections);
    poItems->append(*nmosPolySideConnections);

    delete pmosPolySideConnections;
    delete nmosPolySideConnections;

    return poItems;
}


bool lessBlockingShorterPoly(Metal* po1, Metal *po2)
{
    int blockedByPo1 = thisRouting->countBlocked(po1);
    int blockedByPo2 = thisRouting->countBlocked(po2);

    if(blockedByPo1 < blockedByPo2)
        return true;
    else if(blockedByPo1 > blockedByPo2)
        return false;
    else
        return po1->bottomRight.x() < po2->bottomRight.x();
}

void Routing1::sortByLessBlockingShorterPoly(QList<Metal*> *poItems)
{
    qSort(poItems->begin(), poItems->end(), lessBlockingShorterPoly);
}

void Routing1::setPorpouse(QList<Metal*> *items, int porpouse)
{
    foreach(Metal* m, *items)
        m->porpouse = porpouse;
}

QList<Metal*>* Routing1::insertVerticalPoly(Metal* po)
{
    QList<Transistor*> *transistors = cell->pTransistors;
    QList<Metal*>* vPoItems = new QList<Metal*>();

    if(po->band.compare("NMOS") == 0)
        transistors = cell->nTransistors;

    foreach(Transistor* t, *(transistors))
        if(t->gateNetName.compare(po->net) == 0)
            if(t->x() >= po->x() -1 && t->x() <= po->x() + po->bottomRight.x() + 1)
                vPoItems->append(insertVerticalPoly(t, po));

    return vPoItems;
}

bool Routing1::hasCollidingMetal(QList<Metal*>* poItems1, QList<Metal*>* poItems2)
{
    foreach(Metal* po, *(poItems1))
        if(getCollidingMetal(po,poItems2,Rules::getRule("PO.S.1")))
            return true;

    return false;
}

bool Routing1::insertNonConflictedPolyItems(QList<Metal*>* poToBeInserted)
{
    foreach(Metal* po, *(poToBeInserted))
    {
        QList<Metal*>* vPoItems = insertVerticalPoly(po);
        po->linkedMetal->append(*(vPoItems));
        poToBeInserted->append(*(vPoItems));
        setPorpouse(vPoItems, 2);

        if(hasCollidingMetal(vPoItems, poToBeInserted))
        {
            delete vPoItems;
            return false;
        }

        delete vPoItems;
    }

    return true;
}

void Routing1::fixHorizontalGatePoPosition(QList<Metal*>* poItems)
{
    for(int i=1; i<poItems->size(); i++)
    {
        Metal *po = poItems->at(i);
        QString direction = po->y() < cell->gndRectItem->y() ? "UP" : "DOWN";
        fixMetalPosition(po,poItems,Rules::getRule("PO.S.1"), direction);
    }
}

QList<Metal*>* Routing1::routeBySide()
{
    QList<Metal*>* poToBeInserted = createPolySideConnections();
    setPorpouse(poToBeInserted, 1);

    if(insertNonConflictedPolyItems(poToBeInserted) == false)
    {
        releaseMemory(poToBeInserted);
        return 0;
    }

    return poToBeInserted;
}

QList<Metal*>* Routing1::routeSolutionWithPoly(QList<Metal*>* gateM1Items)
{
    routeVerticalGates(gateM1Items);
    QList<Metal*>* poItems = routeBySide();

    if(poItems)
        poItems->append(*(cell->poItems));

    cell->poItems->clear();

    return poItems;
}

bool Routing1::solveOutsideMetal(QList<Metal*>* solution)
{
    return countOutsideM1(solution) == 0;
}

QList<Metal*>* Routing1::clone(QList<Metal*>* list)
{
    QList<Metal*>* newList = new QList<Metal*>();

    foreach(Metal* m, *(list))
    {
        Metal *newM = new Metal();
        newM->copy(m);

        newList->append(newM);
    }

    return newList;
}

QList<Metal*>* Routing1::getBestSolutionForShorteningGateM1()
{
    sortByYPos(cell->m1Items);
    QList<QList<Metal*>*> *possibleSolutions = getPossibleSolutionsForShorteningGateM1();
    QList<int>* curCombination = new QList<int>();
    QList<Metal*>* bestSolution = 0;
    QList<Metal*>* curSolution;
    QList<Metal*>* polyItems = 0;

    int bestScore = 1e5;

    for(int i=0; i<possibleSolutions->size(); i++)
        curCombination->append(0);

    while(true)
    {
        curSolution = createSolutionForShorteningGateM1(curCombination, possibleSolutions);

        if(solveOutsideMetal(curSolution))
        {
            polyItems = routeSolutionWithPoly(curSolution);

            if(polyItems)
            {
                int curScore = evaluateSolutionForShoteningGateM1(curSolution, polyItems);

                if(curScore < bestScore)
                {
                    bestScore = curScore;
                    releaseMemory(bestSolution);
                    bestSolution = clone(curSolution);
                }

                releaseMemory(polyItems);
                //break;
            }
        }
        releaseMemory(curSolution);

        if(isLastCombination(curCombination, possibleSolutions))
            break;

        getNextCombination(curCombination, possibleSolutions);
    }

    delete curCombination;
    releaseMemory(possibleSolutions);
    return bestSolution;
}

void Routing1::releaseMemory(QList<Metal*>* items)
{
    if(items)
    {
        foreach(Metal* m, *(items))
        {
            if(m)
            {
                delete m->linkedMetal;
                delete m->linkedTransistors;
                delete m;
                m = 0;
            }
        }

        items->clear();

        delete items;
        items = 0;
    }
}
void Routing1::releaseMemory(Metal* m)
{
    delete m->linkedMetal;
    delete m->linkedTransistors;
    delete m;
}

void Routing1::releaseMemory(QList<QList<Metal*>*> *listOfList)
{
    foreach(QList<Metal*>* list, *(listOfList))
        releaseMemory(list);

    delete listOfList;
}

void Routing1::substituteGateM1(QList<Metal*>* curSolution)
{
    foreach(Metal* m1, *(cell->m1Items))
    {
        if(m1->gateM1)
        {
            cell->m1Items->removeOne(m1);
            releaseMemory(m1);
        }
    }

    cell->m1Items->append(*(curSolution));
}

bool Routing1::fixOutsideGates()
{
    QList<Metal*>* solution = getBestSolutionForShorteningGateM1();

    if(!solution || countOutsideM1(solution))
    {
        releaseMemory(solution);
        return false;
    }
    substituteGateM1(solution);
    delete solution;

    QList<Metal*>* gatesM1 = getGatesM1();

    fitToBestPlace(gatesM1);

    QList<Metal*>* poItems = routeSolutionWithPoly(gatesM1);

    delete gatesM1;

    if(poItems)
        cell->poItems->append(*(poItems));
    else
        delete poItems;

    return true;
}

void Routing1::movePolyIn(Metal* po)
{
    qreal previousY = po->y();
    Transistor* greater = getGreaterTransistor((QList<Transistor*>*)(po->linkedTransistors));
    qreal initialY;
    QString direction;

    if(po->y() < cell->nPlusRectItem->y())
    {
        initialY = greater->y() + greater->gateRect.height() - Rules::getRule("PO.O.1") + Rules::getRule("PO.C.1");
        direction = "DOWN";
        po->band = "PMOS";
    }
    else
    {
        initialY = greater->y() + Rules::getRule("PO.O.1") - Rules::getRule("PO.C.1") - Rules::getRule("PO.W.1a");
        direction = "UP";
        po->band = "NMOS";
    }

    po->setY(initialY);

    QList<Metal*>* transistorsPoItems = getTransistorPoItems();
    QList<Metal*>* poItems = new QList<Metal*>();
    poItems->append(*(cell->poItems));
    poItems->append(*transistorsPoItems);


    fixMetalPosition(po,cell->diffItems,Rules::getRule("PO.C.1"), direction);
    fixMetalPosition(po,poItems,Rules::getRule("PO.S.1"), direction);

    Transistor *nt = cell->nTransistors->first();
    Transistor *pt = cell->pTransistors->first();

    if(po->y() > nt->y() + nt->gateRect.height() || po->y() < pt->y() )
        po->setY(previousY);
    else
    {
        foreach(Metal* poi, *(po->linkedMetal))
            cell->poItems->removeOne(poi);

        releaseMemory(po->linkedMetal);
        po->linkedMetal = new QList<Metal*>();

        cell->poItems->append(*(insertVerticalPoly(po)));
    }

    releaseMemory(transistorsPoItems);
    delete poItems;
}

void Routing1::condenseOutsidePoly(QList<Metal*> *outSidePoly, QString band)
{

    int initialIndex;
    int step;
    QList<Transistor*> * transistors;
    qreal initialY;
    QString direction;

    if(band.compare("PMOS") == 0)
    {
        initialIndex = outSidePoly->size() - 1;
        step = -1;
        transistors = cell->pTransistors;
        initialY = transistors->first()->y() + Rules::getRule("PO.O.1") - Rules::getRule("PO.W.1a") - Rules::getRule("PO.C.1");
        direction = "UP";
    }
    else
    {
        initialIndex = 0;
        step = 1;
        transistors = cell->nTransistors;
        initialY = transistors->first()->y() + transistors->first()->gateRect.height() - Rules::getRule("PO.O.1") + Rules::getRule("PO.C.1");
        direction = "DOWN";
    }

    QList<Metal*>* transistorsPoItems = getTransistorPoItems();
    QList<Metal*>* poItems = new QList<Metal*>();
    poItems->append(*(cell->poItems));
    poItems->append(*transistorsPoItems);


    for(int i = initialIndex; i>=0 && i < outSidePoly->size(); i+= step)
    {
        Metal* po = outSidePoly->at(i);
        po->setY(initialY);

        fixMetalPosition(po,poItems,Rules::getRule("PO.S.1"),direction);

        fixVerticalPolyItems(po, band);
    }
}

void Routing1::fixVerticalPolyItems(Metal* po, QString band)
{
    foreach(Metal* vPo, *(po->linkedMetal))
    {
        if(band.compare("PMOS") == 0)
        {
            vPo->setY(po->y());
            vPo->bottomRight.setY(((Transistor*)vPo->linkedTransistors->first())->y() - po->y());
        }
        else
        {
            vPo->bottomRight.setY(po->y() - ((Transistor*)vPo->linkedTransistors->first())->y());
        }
    }
}

QList<Metal*> * Routing1::getOutSidePoly(QString band)
{
    QList<Metal*> *outSidePoly = new QList<Metal*>();

    foreach(Metal* po, *(cell->poItems))
    {
        if(po->porpouse == 1)
        {
            if(band.compare("PMOS") == 0 && po->y() < cell->pTransistors->first()->y())
            {
                outSidePoly->append(po);
            }
            else if(band.compare("NMOS") == 0 && po->y() > cell->nTransistors->first()->y() + cell->nTransistors->first()->gateRect.height())
            {
                outSidePoly->append(po);
            }
        }
    }

    return outSidePoly;
}

void Routing1::condenseOutsidePoly()
{
    QList<Metal*> *pmosOutSidePoly = getOutSidePoly("PMOS");
    QList<Metal*> *nmosOutSidePoly = getOutSidePoly("NMOS");

    sortByYPos(pmosOutSidePoly);
    sortByYPos(nmosOutSidePoly);

    condenseOutsidePoly(pmosOutSidePoly, "PMOS");
    condenseOutsidePoly(nmosOutSidePoly, "NMOS");

    delete pmosOutSidePoly;
    delete nmosOutSidePoly;
}

void Routing1::movePolyIn()
{
    mergeSequencialPo();

    foreach(Metal* po, *(cell->poItems))
        if(po->porpouse == 1)
            movePolyIn(po);

    condenseOutsidePoly();
}

void Routing1::routeGates()
{
    routeGatesWithHorizontalM1();
    fixOutsideGates();
    routeConflictedTransistors();

    //routeGatesBySide();
}

Metal* Routing1::createPoContact(Transistor *t)
{
    Metal* poContact = new Metal();
    poContact->metalType = "PO";
    poContact->bottomRight.setX(Rules::getRule("CO.W.1"));
    poContact->bottomRight.setY(Rules::getRule("CO.W.1"));
    poContact->net = t->gateNetName;

    poContact->setX(t->x() - poContact->bottomRight.x()/2);

    if(t->transistorType.compare("PMOS") == 0)
        poContact->setY(t->y() + t->gateRect.height() - Rules::getRule("PO.O.1") + Rules::getRule("PO.C.1"));
    else
        poContact->setY(t->y() - poContact->bottomRight.y() + Rules::getRule("PO.O.1") - Rules::getRule("PO.C.1"));

    return poContact;
}

void Routing1::routeGatesBySide()
{
    routeGatesBySide(cell->pTransistors);
    routeGatesBySide(cell->nTransistors);

    mergeIdenticalPo();
}

Metal* Routing1::getParallelPo(Metal *po)
{
    foreach(Metal* m, *(cell->poItems))
        if( (po->x() == m->x()) &&
            (po->bottomRight.x() == m->bottomRight.x()) &&
            (po != m) &&
            (m->bottomRight.x() > Rules::getRule("PO.W.1a")))
                return m;

    return 0;
}

void Routing1::mergeParallelPo()
{
    foreach(Metal* po, *(cell->poItems))
    {
        Metal *parallelPo = getParallelPo(po);

        if(parallelPo)
        {
            parallelPo->setY((parallelPo->y() + po->y())/2);
            cell->poItems->removeOne(po);
            releaseMemory(po);
        }
    }
}

Metal* Routing1::getSequencialPo(Metal *po)
{
    foreach(Metal* m, *(cell->poItems))
        if( (po->y() == m->y()) &&
            (po->bottomRight.y() >= m->bottomRight.y()) &&
            (po != m) &&
            (po->x() <= m->x()) &&
            (po->x() + po->bottomRight.x() >= m->x()) &&
            (m->porpouse == 1))
                return m;

    return 0;
}

void Routing1::mergeSequencialPo()
{
    foreach(Metal* po, *(cell->poItems))
    {
        if(po->porpouse == 1)
        {
            po->bottomRight.setY(Rules::getRule("PO.W.1a"));

            Metal* seqPo = getSequencialPo(po);

            if(seqPo)
            {
                qreal x0 = po->x() < seqPo->x() ? po->x() : seqPo->x();
                qreal x1 = po->x() + po->bottomRight.x() > seqPo->x() + seqPo->bottomRight.x() ? po->x() + po->bottomRight.x() : seqPo->x() + seqPo->bottomRight.x();

                seqPo->setX(x0);
                seqPo->bottomRight.setX(x1 - x0);

                seqPo->linkedMetal->append(*(po->linkedMetal));
                seqPo->linkedTransistors->append(*(po->linkedTransistors));
                cell->poItems->removeOne(po);

                releaseMemory(po);
            }
        }
    }
}

void Routing1::mergeIdenticalPo()
{
    mergeSequencialPo();
    mergeParallelPo();
}

void Routing1::routeGatesBySide(QList<Transistor*> *transistors)
{
    for(int i=1; i<transistors->size() -1; i++)
        routeGatesBySide(transistors, 1);
}

void Routing1::routeGatesBySide(QList<Transistor*> *transistors, int distance)
{
    QString direction = "UP";
    if(transistors->first()->transistorType.compare("PMOS") == 0)
        direction = "DOWN";

    QList<Metal*>* transistorsPoItems = getTransistorPoItems();
    QList<Metal*>* poItems = new QList<Metal*>();
    poItems->append(*(cell->poItems));
    poItems->append(*transistorsPoItems);

    for(int i=0; i + distance <transistors->size(); i++)
    {
        Transistor* cur = transistors->at(i);
        Transistor* next = transistors->at(i + distance);

        if(cur->gateNetName.compare(next->gateNetName) == 0 && cur->routedWithPo == false)
        {
            Metal *po = insertHorizontalPoly(cur, next, poItems, 0, direction);

            if(po->y() < cell->pTransistors->first()->y() ||
               po->y() > cell->nTransistors->first()->y() + cell->nTransistors->first()->gateRect.height())
                continue;

            Metal* poV1 = insertVerticalPoly(cur, po);
            Metal* poV2 = insertVerticalPoly(next, po);

            if(getCollidingMetal(poV1, poItems, Rules::getRule("PO.S.1")) ||
               getCollidingMetal(poV2, poItems, Rules::getRule("PO.S.1")))
            {
                releaseMemory(poV1);
                releaseMemory(poV2);
                releaseMemory(po);

                continue;
            }

            cell->poItems->append(po);
            cell->poItems->append(poV1);
            cell->poItems->append(poV2);

            cur->routedWithPo = true;
        }
    }

    releaseMemory(transistorsPoItems);
    delete poItems;
}

Metal* Routing1::insertVerticalPoly(Transistor* t, Metal* po)
{
    qreal y0, y1;

    if(t->y() < po->y())
    {
        y0 = t->y();
        y1 = po->y();
    }
    else
    {
        y0 = po->y();
        y1 = t->y();
    }

    Metal* newPo = new Metal();

    newPo->metalType = "PO";
    newPo->net = t->gateNetName;
    newPo->bottomRight = QPointF(Rules::getRule("PO.W.1a"),y1 - y0);
    newPo->setPos(t->x() - Rules::getRule("PO.W.1a")/2, y0);
    newPo->linkedTransistors->append(t);
    t->routedWithPo = true;

    return newPo;
}

Metal* Routing1::getGateM1(QString net, QList<Metal*>* m1Items)
{
    foreach(Metal *m, *(m1Items))
        if(m->gateM1 && m->net.compare(net) == 0)
            return m;

    return 0;
}

void Routing1::routeVerticalGate(Transistor *t, QList<Metal*> *m1Items)
{
    Metal* gateM1 = getGateM1(t->gateNetName, m1Items);
    t->routed = false;

    if(gateM1->x() > t->x() || t->x() > gateM1->x() + gateM1->bottomRight.x())
        return;

    qreal m1Extension = (Rules::getRule("CO.E.2")*2 + Rules::getRule("CO.W.1") - Rules::getRule("M1.W.1"))/2;

    qreal y0 = gateM1->y() < t->getGatePos().y() ? gateM1->y() - m1Extension: t->getGatePos().y();
    qreal y1 = gateM1->y() > t->getGatePos().y() ? gateM1->y() + gateM1->bottomRight.y() + m1Extension : t->getGatePos().y();

    Metal* po = new Metal();
    po->net = t->gateNetName;
    po->metalType = "PO";
    po->bottomRight.setX(Rules::getRule("PO.W.1a"));
    po->bottomRight.setY(y1- y0);
    po->setPos(t->getGatePos().x(), y0);

    t->routed = true;
    po->linkedTransistors->append(t);
    po->linkedMetal->append(gateM1);
    po->porpouse = 3;
    po->gateM1 = true;
    cell->poItems->append(po);
}

void Routing1::routeVerticalGates(QList<Transistor*> *transistors, QList<Metal *> *m1Items)
{
    foreach(Transistor* t, *(transistors))
        routeVerticalGate(t, m1Items);
}

QList<Transistor*>* Routing1::getConflictedTransistors(QList<Transistor*>* transistors)
{
    QList<Transistor*> *conflicted = new QList<Transistor*>();

    foreach(Transistor* t, *(transistors))
        if(hasOppositeGateConflict(t,cell->m1Items))
            conflicted->append(t);

    return conflicted;
}

QList<Transistor*>* Routing1::getConflictedTransistors()
{
    QList<Transistor*> *conflicted = new QList<Transistor*>();

    QList<Metal*>* transistorsPoItems = getTransistorPoItems();
    QList<Metal*>* poItems = new QList<Metal*>();
    poItems->append(*(cell->poItems));
    poItems->append(*transistorsPoItems);

    foreach(Metal* po, *(cell->poItems))
        if(po->linkedTransistors->size() == 1 && getCollidingMetal(po,poItems,Rules::getRule("PO.S.1")))
            conflicted->append((Transistor*)(po->linkedTransistors->first()));

    /*QList<Transistor*> *conflicted = getConflictedTransistors(cell->pTransistors);

    QList<Transistor*> *nmosConflicted = getConflictedTransistors(cell->nTransistors);
    conflicted->append(*nmosConflicted);

    delete nmosConflicted;*/

    releaseMemory(transistorsPoItems);
    return conflicted;
}

QList<Transistor*>* Routing1::getComplement(QList<Transistor*>* transistors, QList<Transistor*>* cellTransistors)
{
    QList<Transistor*> *complement = new QList<Transistor*>();

    foreach(Transistor* t, *(cellTransistors))
        if(transistors->contains(t) == false)
            complement->append(t);

    return complement;
}

QList<Transistor*>* Routing1::getComplement(QList<Transistor*>* transistors)
{
    QList<Transistor*> *complement = getComplement(transistors, cell->pTransistors);

    QList<Transistor*> *nmosComplement = getComplement(transistors, cell->nTransistors);
    complement->append(*nmosComplement);

    delete nmosComplement;
    return complement;
}

void Routing1::fixPosIndexDueToGap(Transistor* t)
{
    QList<Transistor*>* transistors = getTransistorsList(t);
    QList<Transistor*>* oppositeTransistors = getOppositeTransistorsList(t);

    foreach(Transistor *ti, *(oppositeTransistors))
        if(ti->posIndex > t->posIndex)
            ti->posIndex++;

    foreach(Transistor *ti, *(transistors))
        if(ti->posIndex >= t->posIndex)
            ti->posIndex++;
}

void Routing1::removeContacts(Metal* m)
{
    foreach(Metal* c, *(cell->coItems))
    {
        if(c->collidesWithItem(m))
        {
            cell->coItems->removeOne(c);
            releaseMemory(c);
        }
    }
}

void Routing1::fixGateM1(Metal* m)
{
    removeContacts(m);
    QList<Metal*>* contacts = insertGateContacts(m->net);
    m = insertHorizontalM1(contacts,m->y(), "DOWN");
}

void Routing1::fixGatePolyDueToGap()
{
    foreach(Metal* po, *(cell->poItems))
    {
        if(po->linkedTransistors->empty() == false)
            po->setX(((Transistor*)po->linkedTransistors->first())->x() - Rules::getRule("PO.W.1a")/2);

        if(po->linkedMetal->empty() == false)
            po->setX(po->linkedMetal->first()->x());
    }
}

void Routing1::fixGateM1DueToGap()
{
    foreach(Metal* m, *(cell->m1Items))
        fixGateM1(m);
}

void Routing1::insertGap(Transistor* t)
{
    fixPosIndexDueToGap(t);
    cell->refreshScenePositions();
    //fixGateM1DueToGap();
    //fixGatePolyDueToGap();
    //fixContactPositionDueToGap(t);
}

Transistor* Routing1::routeBySibling(Transistor* t)
{
    Transistor* sibling = getLessBlockingClosestSibling(t);

    if(sibling)
    {
        Transistor* t1 = t->posIndex < sibling->posIndex ? t : sibling;
        Transistor* t2 = t->posIndex > sibling->posIndex ? t : sibling;

        qreal initialY;
        QString direction;

        if(t->transistorType.compare("PMOS") == 0)
        {
            initialY = t->y() + Rules::getRule("PO.O.1") - Rules::getRule("PO.C.1");
            direction = "UP";
        }
        else
        {
            initialY = t->y() + t->gateRect.height() - Rules::getRule("PO.O.1") + Rules::getRule("PO.C.1");
            direction = "DOWN";
        }

        QList<Metal*>* transistorsPoItems = getTransistorPoItems();
        QList<Metal*>* poItems = new QList<Metal*>();
        poItems->append(*(cell->poItems));
        poItems->append(*transistorsPoItems);

        Metal* po = insertHorizontalPoly(t1,t2, poItems, initialY, direction);
        po->band = t1->transistorType;

        QList<Metal*>* vPoItems = insertVerticalPoly(po);

        if(!vPoItems || hasCollidingMetal(vPoItems,poItems))
        {
            releaseMemory(po);
            //'delete sibling;

            if(vPoItems)
                releaseMemory(vPoItems);

            sibling = 0;
        }
        else
        {
            cell->poItems->append(po);
            cell->poItems->append(*vPoItems);
        }

        delete vPoItems;
        delete poItems;
        releaseMemory(transistorsPoItems);
    }
    return sibling;
}

void Routing1::removeGateVerticalPo(Transistor* t)
{
    foreach(Metal* po, *(cell->poItems))
    {
        if(po->linkedTransistors->contains(t) && po->gateM1)
        {
            cell->poItems->removeOne(po);
            releaseMemory(po);
            break;
        }
    }
}

Transistor* Routing1::getBestSiblingToRoute(Transistor* t)
{
    QList<Transistor*>* siblings = getAllTransistorSiblings(t);

    int bestScore = 1e5;
    Transistor* bestSibling = 0;

    foreach(Transistor* sibling, *(siblings))
    {
        int curScore = evaluateTransistorRouting(sibling, t);

        if(curScore < bestScore)
        {
            bestSibling = sibling;
            bestScore = curScore;
        }
    }
    delete siblings;
    return bestSibling;
}

bool Routing1::routeTransistors(Transistor* t1, Transistor* t2)
{
    Transistor* left =  t1->posIndex < t2->posIndex ? t1 : t2;
    Transistor* right = t1->posIndex >= t2->posIndex ? t1 : t2;

    QList<Metal*>* transistorPoItems = getTransistorPoItems();
    QList<Metal*>* poItems = new QList<Metal*>();
    poItems->append(*(cell->poItems));
    poItems->append(*transistorPoItems);
    Metal* hPo = 0;
    int porpouse = 0;

    if(t1->transistorType.compare(t2->transistorType) == 0)
    {
        porpouse = 1;
        qreal initialYUp;
        qreal initialYDown;
        Transistor* greater = getGreaterTransistor(t1,t2);

        if(t1->transistorType.compare("PMOS") == 0)
        {
            initialYUp = t1->y();
            initialYDown = greater->y() + greater->gateRect.height();
        }
        else
        {
            initialYUp = greater->y();
            initialYDown = t1->y() + greater->gateRect.height();
        }

        Metal* upPo = insertHorizontalPoly(left, right, poItems, initialYUp, "UP");
        Metal* downPo = insertHorizontalPoly(left, right, poItems, initialYDown, "DOWN");

        if(t1->transistorType.compare("PMOS") == 0)
        {
            if(canBeRouted(upPo, poItems, left, right))
            {
                hPo = upPo;
                releaseMemory(downPo);

            }
            else if(canBeRouted(downPo,poItems,  left, right))
            {
                hPo = downPo;
                releaseMemory(upPo);
            }
        }
        else
        {
            if(canBeRouted(downPo,poItems,  left, right))
            {
                hPo = downPo;
                releaseMemory(upPo);

            }
            else if(canBeRouted(upPo, poItems, left, right))
            {
                hPo = upPo;
                releaseMemory(downPo);
            }
        }
    }
    else
    {
        qreal initialY = left->y() < right->y() ? left->y() : right->y();
        qreal maxY = left->y() > right->y() ? left->y() : right->y();
        hPo = insertHorizontalPoly(left, right, poItems, initialY, "DOWN");

        if(hPo->y() > maxY || canBeRouted(hPo, poItems, left, right) == false)
            hPo = 0;
    }

    bool ret = false;
    if(hPo)
    {
        Metal* vPo1 = insertVerticalPoly(left, hPo);
        Metal* vPo2 = insertVerticalPoly(right, hPo);

        cell->poItems->append(vPo1);
        cell->poItems->append(vPo2);
        cell->poItems->append(hPo);

        hPo->linkedMetal->append(vPo1);
        hPo->linkedMetal->append(vPo2);
        hPo->linkedTransistors->append((Transistor*)left);
        hPo->linkedTransistors->append((Transistor*)right);
        hPo->porpouse = porpouse;

        ret = true;
    }
    releaseMemory(transistorPoItems);
    delete poItems;

    return ret;
}

bool Routing1::routeConflictedTransistor(Transistor* t)
{
    Transistor* sibling = getBestSiblingToRoute(t);

    if(sibling)
        if(routeTransistors(t,sibling))
            t->routed = true;

    removeGateVerticalPo(t);

    return t->routed;
}

void Routing1::setNotRouted(QList<Transistor*>*  transistors)
{
    foreach(Transistor* t, *(transistors))
        t->routed = false;
}

Transistor* Routing1::getOppositeLeftSibling(Transistor *t)
{
    QList<Transistor*>*  oppositeTransistors = getOppositeTransistorsList(t);
    Transistor* leftSibling = 0;

    foreach(Transistor* ti, *(oppositeTransistors))
    {
        if(ti->gateNetName.compare(t->gateNetName) == 0 && ti->routed)
        {
            if(ti->posIndex >= t->posIndex)
                break;

            leftSibling = ti;
        }
    }
    return leftSibling;
}

Transistor* Routing1::getOppositeRightSibling(Transistor *t)
{
    QList<Transistor*>*  oppositeTransistors = getOppositeTransistorsList(t);
    Transistor* rightSibling = 0;

    for(int i=oppositeTransistors->size() - 1; i>0; i--)
    {
        Transistor* ti = oppositeTransistors->at(i);

        if(ti->gateNetName.compare(t->gateNetName) == 0 && ti->routed)
        {
            if(ti->posIndex <= t->posIndex)
                break;

            rightSibling = ti;
        }
    }
    return rightSibling;
}

QList<Transistor*>* Routing1::getAllTransistorSiblings(Transistor *t)
{
    QList<Transistor*>* transistors = getTransistorsList(t);

    Transistor* leftSibling = getLeftSibling(transistors, t);
    Transistor* rightSibling = getRightSibling(transistors, t);
    Transistor* oppositeLeftSibling = getOppositeLeftSibling(t);
    Transistor* oppositeRightSibling = getOppositeRightSibling(t);

    QList<Transistor*>* retSiblings = new QList<Transistor*>();

    if(leftSibling)
        retSiblings->append(leftSibling);

    if(rightSibling)
        retSiblings->append(rightSibling);

    if(oppositeLeftSibling)
        retSiblings->append(oppositeLeftSibling);

    if(oppositeRightSibling)
        retSiblings->append(oppositeRightSibling);

    return retSiblings;
}

Transistor* Routing1::getGreaterTransistor(QList<Transistor*>* transistors)
{
    Transistor* greater = transistors->first();

    foreach(Transistor* t, *(transistors))
        if(greater->gateRect.height() < t->gateRect.height())
            greater = t;

    return greater;
}

Transistor* Routing1::getGreaterTransistor(Transistor *t1, Transistor *t2)
{
    if(t1->gateRect.height() > t2->gateRect.height())
        return t1;

    return t2;
}

bool Routing1::canBeRouted(Metal* hPo, QList<Metal*>* poItems, Transistor *t1, Transistor *t2)
{
    Metal* t1VPo = insertVerticalPoly(t1, hPo);
    bool ret = true;

    if(getCollidingMetal(t1VPo,poItems,Rules::getRule("PO.S.1")))
        ret = false;

    Metal* t2VPo = insertVerticalPoly(t2, hPo);

    if(getCollidingMetal(t2VPo,poItems,Rules::getRule("PO.S.1")))
        ret = false;

    releaseMemory(t1VPo);
    releaseMemory(t2VPo);

    return ret;
}

int Routing1::evaluateTransistorRouting(Transistor *t1, Transistor *t2)
{
    Transistor* left =  t1->posIndex < t2->posIndex ? t1 : t2;
    Transistor* right = t1->posIndex >= t2->posIndex ? t1 : t2;
    int score = 1e7;

    QList<Metal*>* poItems = new QList<Metal*>();
    QList<Metal*>* transistorPoItems = getTransistorPoItems();
    poItems->append(*(cell->poItems));
    poItems->append(*transistorPoItems);

    if(t1->transistorType.compare(t2->transistorType) == 0)
    {
        qreal initialYUp;
        qreal initialYDown;
        Transistor* greater = getGreaterTransistor(t1,t2);

        if(t1->transistorType.compare("PMOS") == 0)
        {
            initialYUp = t1->y();
            initialYDown = greater->y() + greater->gateRect.height();
        }
        else
        {
            initialYUp = greater->y();
            initialYDown = t1->y() + greater->gateRect.height();
        }

        Metal* upPo = insertHorizontalPoly(left, right, poItems, initialYUp, "UP");
        Metal* downPo = insertHorizontalPoly(left, right, poItems, initialYDown, "DOWN");

        if(canBeRouted(upPo, poItems, left, right) || canBeRouted(downPo,poItems,  left, right))
            score = countBlocked(left, right);

        releaseMemory(upPo);
        releaseMemory(downPo);
    }
    else
    {
        qreal initialY = left->y() < right->y() ? left->y() : right->y();
        qreal maxY = left->y() > right->y() ? left->y() : right->y();
        Metal* po = insertHorizontalPoly(left, right, poItems, initialY, "DOWN");

        if(po->y() > maxY)
            score = 1e7;
        else
            score = countBlocked(t1, t2);

        releaseMemory(po);
    }
    releaseMemory(transistorPoItems);
    delete poItems;

    return score + right->posIndex - left->posIndex;
}

int Routing1::evaluateTransistorRouting(Transistor *t)
{
    QList<Transistor*>* siblings = getAllTransistorSiblings(t);

    int bestScore = 1e9;

    foreach(Transistor* sibling, *(siblings))
    {
        int curScore = evaluateTransistorRouting(sibling, t);

        if(curScore < bestScore)
            bestScore = curScore;
    }

    delete siblings;
    return bestScore;
}

Transistor* Routing1::getLessBlockingTransistorToRoute(QList<Transistor*>*  conflictedTransistors)
{
    Transistor* bestTransistor = 0;
    int bestScore = 1e7;

    foreach(Transistor* curTransistor, *(conflictedTransistors))
    {
        int curScore = evaluateTransistorRouting(curTransistor);

        if(curScore < bestScore)
        {
            bestTransistor = curTransistor;
            bestScore = curScore;
        }
    }

    return bestTransistor;
}

bool Routing1::isOverOppositeTransistor(Transistor*  t)
{
    Transistor* oppositeTransistor = getOppositeTransistor(t);
    Metal* oppositePo = getPoItem(oppositeTransistor);
    oppositePo->bottomRight.setY(oppositePo->bottomRight.y() + 2*Rules::getRule("PO.S.1"));
    oppositePo->setY(oppositePo->y() - Rules::getRule("PO.S.1"));
    bool ret = false;

    foreach(Metal* po, *(cell->poItems))
    {
        if(po->linkedTransistors->contains(t) && po->gateM1 )
        {
            if(po->collidesWithItem(oppositePo))
                ret = true;

            break;
        }
    }

    releaseMemory(oppositePo);
    return ret;
}

void Routing1::routeConflictedTransistors(QList<Transistor*>*  conflictedTransistors)
{
    setNotRouted(conflictedTransistors);

    while(conflictedTransistors->size() > 0)
    {
        Transistor* t = getLessBlockingTransistorToRoute(conflictedTransistors);

        if(!t || routeConflictedTransistor(t) == false)
            break;

        conflictedTransistors->removeOne(t);

        Transistor* oppositeTransistor = getOppositeTransistor(t);

        if(isOverOppositeTransistor(oppositeTransistor) == false)
            conflictedTransistors->removeOne(oppositeTransistor);
    }

    if(conflictedTransistors->empty() == false)
    {
        foreach(Transistor *t, *conflictedTransistors)
            insertGap(t);

        reRoute();
    }
}

void Routing1::routeConflictedTransistors()
{
    QList<Transistor*>* conflictedTransistors = getConflictedTransistors();

    //sortByLessBlockingClosestSibling(conflictedTransistors);
    routeConflictedTransistors(conflictedTransistors);

    delete conflictedTransistors;
}

bool Routing1::hasRoutedSibling(Transistor* t)
{
    QList<Transistor*>* transistors = getTransistorsList(t);

    foreach(Transistor* ti, *(transistors))
        if(ti != t && ti->gateNetName.compare(t->gateNetName) == 0 && ti->routed)
            return true;

    return false;
}

QList<Transistor*>* Routing1::getTransistorsWithoutRoutedSibling(QList<Transistor*>*  conflictedTransistors)
{
    QList<Transistor*>* transistorsWithoutRoutedSibling = new QList<Transistor*>();

    foreach(Transistor* t, *(conflictedTransistors))
        if(hasRoutedSibling(t) == false)
            transistorsWithoutRoutedSibling->append(t);

    return transistorsWithoutRoutedSibling;
}

Transistor* Routing1::getTransistorByGate(int initialIndex, QString gateNet, int step, QList<Transistor*>*  transistors)
{
    for(int i = initialIndex; i>=0 && i < transistors->size(); i+=step)
    {
        Transistor* ti = transistors->at(i);

        if(ti->gateNetName.compare(gateNet) == 0)
            return ti;
    }

    return 0;
}

Transistor* Routing1::getTransistorByGate(int initialIndex, Transistor* t, int step, bool byPosIndex)
{
    QList<Transistor*>* transistors = getTransistorsList(t);

    int size = transistors->size() - 1;

    if(byPosIndex)
        size = transistors->last()->posIndex;

    for(int i = initialIndex; i>=0 && i <= size; i+=step)
    {
        Transistor* ti = transistors->at(i);

        if(byPosIndex)
            ti = cell->getTransistorByPosIndex(transistors,i);

        if(ti && ti->gateNetName.compare(t->gateNetName) == 0)
            return ti;
    }

    return 0;
}

Transistor* Routing1::getMostCenteredTransistor(Transistor* t)
{
    QList<Transistor*>* transistors = getTransistorsList(t);

    Transistor* first = getTransistorByGate(0,t,1, false);
    Transistor* last = getTransistorByGate(transistors->size()-1,t,-1, false);

    int middle = (last->posIndex + first->posIndex)/2;

    Transistor* middleLeft = getTransistorByGate(middle,t,-1, true);
    Transistor* middleRight = getTransistorByGate(middle,t,1, true);

    if(middle - middleLeft->posIndex < middleRight->posIndex - middle)
        return middleLeft;
    else
        return middleRight;
}

void Routing1::removeTransistorsWithSimilarGate(QList<Transistor*>*  transistorsWithoutRoutedSibling, Transistor* t)
{
    foreach(Transistor* ti, *(transistorsWithoutRoutedSibling))
        if(ti->gateNetName.compare(t->gateNetName) == 0 && ti->transistorType.compare(t->transistorType) == 0)
            transistorsWithoutRoutedSibling->removeOne(ti);
}


void Routing1::solveGateWithoutRoutedSibling(QList<Transistor*>*  conflictedTransistors)
{
    QList<Transistor*>*  transistorsWithoutRoutedSibling = getTransistorsWithoutRoutedSibling(conflictedTransistors);

    foreach(Transistor* t, *(transistorsWithoutRoutedSibling))
    {
        Transistor* oppositeTransistor = getOppositeTransistor(t);

        if(transistorsWithoutRoutedSibling->contains(oppositeTransistor))
        {
            Transistor* mostCentered = getMostCenteredTransistor(t);
            insertGap(mostCentered);
            routeVerticalGate(mostCentered, cell->m1Items);
            removeTransistorsWithSimilarGate(transistorsWithoutRoutedSibling, t);
        }
    }
}

void Routing1::routeVerticalGates(QList<Metal*>* m1Items)
{
    routeVerticalGates(cell->pTransistors, m1Items);
    routeVerticalGates(cell->nTransistors, m1Items);
}

Metal* Routing1::insertHorizontalPoly(Transistor* t1, Transistor* t2, QList<Metal*>* poItems, qreal initialY,  QString direction)
{
    Metal* po = new Metal();

    po->metalType = "PO";
    po->net = t1->gateNetName;
    po->bottomRight = QPointF(t2->x() - t1->x() + Rules::getRule("PO.W.1a"),Rules::getRule("PO.W.1a"));
    po->setPos(t1->x() - Rules::getRule("PO.W.1a")/2, initialY);

    fixMetalPosition(po, cell->diffItems, Rules::getRule("PO.C.1"), direction);
    fixMetalPosition(po, poItems, Rules::getRule("PO.S.1"), direction);

    return po;
}

QList<Metal*>* Routing1::getTransistorPoItems()
{
    QList<Metal*>* retPoItems = new QList<Metal*>();

    QList<Metal*>* pmosPoItems = getPoItems(cell->pTransistors);
    retPoItems->append(*pmosPoItems);

    QList<Metal*>* nmosPoItems = getPoItems(cell->nTransistors);
    retPoItems->append(*nmosPoItems);

    delete pmosPoItems;
    delete nmosPoItems;
    return retPoItems;
}

Metal* Routing1::getPoItem(Transistor *t)
{
    Metal *po = new Metal();
    po->net = t->gateNetName;
    po->bottomRight.setX(t->gateRect.width());
    po->bottomRight.setY(t->gateRect.height());
    po->setPos(t->pos());
    po->setX(po->x() - Rules::getRule("PO.W.1a")/2);

    return po;
}

QList<Metal*>* Routing1::getPoItems(QList<Transistor*> *transistors)
{
    QList<Metal*>* poItems = new QList<Metal*>();

    foreach(Transistor *t, *(transistors))
        poItems->append(getPoItem(t));

    return poItems;
}

bool Routing1::fixMetalPosition(Metal* m, QList<Metal*> *items, qreal spacingRule, QString direction)
{
    bool translated = false;

    while(true)
    {
        Metal *collidingMetal = getCollidingMetal(m, items, spacingRule);

        if(collidingMetal)
        {
            translated = true;
            if(direction.compare("DOWN") == 0)
                m->setY(collidingMetal->y() + collidingMetal->bottomRight.y() + spacingRule);
            else if(direction.compare("UP") == 0)
                m->setY(collidingMetal->y() - m->bottomRight.y() -spacingRule);
            else if(direction.compare("LEFT") == 0)
                m->setX(collidingMetal->x() - m->bottomRight.x() -spacingRule);
            else
                m->setX(collidingMetal->x() + collidingMetal->bottomRight.x() +spacingRule);
        }
        else
            break;
    }

    return translated;
}

void Routing1::insertVerticalPoly(Transistor* pt, Transistor* nt)
{
    Metal* po = new Metal();

    po->metalType = "PO";
    po->net = pt->gateNetName;
    po->bottomRight = QPointF(Rules::getRule("PO.W.1a"),nt->y() - (pt->y() + pt->gateRect.height()));
    po->setPos(pt->x() - Rules::getRule("PO.W.1a")/2, pt->y() + pt->gateRect.height());

    cell->poItems->append(po);
}

void Routing1::resetRouting()
{
    resetFlags();

    releaseMemory(cell->diffItems);
    releaseMemory(cell->coItems);
    releaseMemory(cell->poItems);
    releaseMemory(cell->m2Items);

    cell->diffItems = new QList<Metal*>();
    cell->coItems   = new QList<Metal*>();
    cell->poItems   = new QList<Metal*>();
    cell->m2Items   = new QList<Metal*>();

    foreach(Metal *m, *(cell->m1Items))
    {
        if(m != cell->gndRectItem && m != cell->vccRectItem)
        {
            cell->m1Items->removeOne(m);
            releaseMemory(m);
        }
    }
}
void Routing1::resetFlags()
{
    foreach(Transistor *t, *(cell->pTransistors))
    {
        t->routedWithPo = false;
    }

    foreach(Transistor *t, *(cell->nTransistors))
    {
        t->routedWithPo = false;
    }
}

void Routing1::internRouting()
{
    internRouting(cell->nTransistors);
    internRouting(cell->pTransistors);
}

void Routing1::internRouting(QList<Transistor*> *transistors)
{
    QStringList *internNets = getInternNets(transistors);
    sortByWidth(internNets);
    insertHorizontalM1Nets(internNets, transistors);
    delete internNets;
}

bool lessThanWidth(QString net1, QString net2)
{
    return thisRouting->getNetWidth(net1) > thisRouting->getNetWidth(net2);
}

qreal Routing1::getNetWidth(QString net)
{
    return getLastXOcurrency(net,true, true) - getFirstXOcurrency(net, true, true);
}

qreal Routing1::getFirstXOcurrency(QString net, bool compareDiff, bool compareGate)
{
    qreal xp = getFirstXOcurrency(net, cell->pTransistors, compareDiff, compareGate);
    qreal xn = getFirstXOcurrency(net, cell->nTransistors, compareDiff, compareGate);

    if(xp < xn && xp != 0)
        return xp;

    return xn;
}

qreal Routing1::getLastXOcurrency(QString net, bool compareDiff, bool compareGate)
{

    qreal xp = getLastXOcurrency(net, cell->pTransistors, compareDiff, compareGate);
    qreal xn = getLastXOcurrency(net, cell->nTransistors, compareDiff, compareGate);

    if(xp > xn)
        return xp;

    return xn;
}

qreal Routing1::getFirstXOcurrency(QString net, QList<Transistor*> *transistors, bool compareDiff, bool compareGate)
{
    foreach(Transistor* t, *(transistors))
    {
        if(compareDiff)
        {
            if(t->sourceNetName.compare(net) == 0)
                return t->getSourceContPos().x();

            if(t->drainNetName.compare(net) == 0)
                return t->getDrainContPos().x();
        }

        if(compareGate && t->gateNetName.compare(net) == 0)
            return t->x();
    }

    return 0;
}

qreal Routing1::getLastXOcurrency(QString net, QList<Transistor*> *transistors,bool compareDiff, bool compareGate)
{
    for(int i= transistors->size() -1; i>=0; i--)
    {
        Transistor *t = transistors->at(i);

        if(compareDiff)
        {
            if(t->sourceNetName.compare(net) == 0)
                return t->getSourceContPos().x();

            if(t->drainNetName.compare(net) == 0)
                return t->getDrainContPos().x();
        }

        if(compareGate)
            if(t->gateNetName.compare(net) == 0)
                return t->x();
    }

    return 0;
}

QList<Transistor*>* Routing1::getOppositeTransistorsList(Transistor* t)
{
    if(t->transistorType.compare("NMOS") == 0)
        return cell->pTransistors;
    else
        return cell->nTransistors;
}

QList<Transistor*>* Routing1::getTransistorsList(Transistor* t)
{
    if(t->transistorType.compare("PMOS") == 0)
        return cell->pTransistors;
    else
        return cell->nTransistors;
}

Transistor* Routing1::getSibling(QList<Transistor*>* transistors, Transistor* t, int step)
{
    int tIndex = transistors->indexOf(t);
    for(int i = tIndex+step; i < transistors->size() && i >=0; i+=step)
    {
        Transistor* sibling = transistors->at(i);

        if(sibling && sibling->routed && sibling->gateNetName.compare(t->gateNetName) == 0)
            return sibling;
    }

    return 0;
}

Transistor* Routing1::getRightSibling(QList<Transistor*>* transistors, Transistor* t)
{
    return getSibling(transistors, t, 1);
}

Transistor* Routing1::getLeftSibling(QList<Transistor*>* transistors, Transistor* t)
{
    return getSibling(transistors, t, -1);
}

bool Routing1::hasRoutedSiblingBetween(Transistor* t1, Transistor* t2)
{
    QList<Transistor*>* transistors = getTransistorsList(t1);

    for(int i= transistors->indexOf(t1) + 1; i< transistors->indexOf(t2); i++)
        if(transistors->at(i)->routed == true)
            return true;

    return false;
}

int Routing1::countBlocked(Metal* po)
{
    Transistor* t1 = (Transistor*)(po->linkedTransistors->first());
    Transistor* t2 = (Transistor*)(po->linkedTransistors->last());

    return countBlocked(t1, t2);
}

int Routing1::countBlocked(Transistor* t1, Transistor* t2)
{
    Transistor* left =  t1->posIndex < t2->posIndex ? t1 : t2;
    Transistor* right = t1->posIndex >= t2->posIndex ? t1 : t2;

    QList<Transistor*>* transistors = getTransistorsList(t1);

    int blocked = 0;

    foreach(Transistor* ti, *(transistors))
        if(ti->posIndex >= left->posIndex && ti->posIndex <= right->posIndex && ti->gateNetName.compare(t1->gateNetName) != 0)
            if(ti->routed == false)
                blocked++;

    /*if(t1->transistorType.compare(t2->transistorType) != 0)
    {
        transistors = getTransistorsList(t2);

        foreach(Transistor* ti, *(transistors))
            if(ti->posIndex > left->posIndex && ti->posIndex < right->posIndex && ti->gateNetName.compare(t1->gateNetName) != 0)
                if(ti->routed == false)
                    blocked++;
    }*/

    return blocked;
}

bool lessBlockingClosestSibling(Transistor* t1, Transistor *t2)
{
    Transistor* lessBlockingClosestSiblingT1 = thisRouting->getLessBlockingClosestSibling(t1);
    Transistor* lessBlockingClosestSiblingT2 = thisRouting->getLessBlockingClosestSibling(t2);

    if(!lessBlockingClosestSiblingT1 || !lessBlockingClosestSiblingT2)
        return false;

    int siblingDistanceT1 = abs(lessBlockingClosestSiblingT1->posIndex - t1->posIndex);
    int siblingDistanceT2 = abs(lessBlockingClosestSiblingT2->posIndex - t2->posIndex);

    int blockedByT1 = thisRouting->countBlocked(t1, lessBlockingClosestSiblingT1);
    int blockedByT2 = thisRouting->countBlocked(t2, lessBlockingClosestSiblingT2);

    if(blockedByT1 < blockedByT2)
        return true;
    else if(blockedByT1 > blockedByT2)
        return false;
    else
        return siblingDistanceT1 < siblingDistanceT2;
}

Transistor* Routing1::getLessBlockingClosestSibling(Transistor* t)
{
    QList<Transistor*> *transistors = getTransistorsList(t);
    Transistor* leftSibling = getLeftSibling(transistors, t);
    Transistor* rightSibling = getRightSibling(transistors, t);

    if(!leftSibling)
        return rightSibling;

    if(!rightSibling)
        return leftSibling;

    int blockedByLeft = countBlocked(leftSibling, leftSibling);
    int blockedByRight = countBlocked(t, rightSibling);

    if(blockedByLeft < blockedByRight)
        return leftSibling;
    else if(blockedByLeft > blockedByRight)
        return rightSibling;
    else if(t->posIndex - leftSibling->posIndex < rightSibling->posIndex - t->posIndex)
        return leftSibling;
    else
        return rightSibling;
}

void Routing1::sortByLessBlockingClosestSibling(QList<Transistor *> *transistors)
{
    qSort(transistors->begin(), transistors->end(), lessBlockingClosestSibling);
}

void Routing1::sortByWidth(QStringList *internNets)
{
    qSort(internNets->begin(), internNets->end(), lessThanWidth);
}

void Routing1::insertHorizontalM1Nets(QStringList *internNets, QList<Transistor*> *transistors)
{
    foreach(QString net, *(internNets))
        insertHorizontalM1Net(net, transistors);
}

void Routing1::insertHorizontalM1Net(QString net, QList<Transistor*> *transistors)
{
    QList<Metal*> *contacts = insertContacts(net, transistors);

    foreach(Metal* c, *(contacts))
        cell->coItems->append(c);

    Metal* m1;

    if(transistors->first()->transistorType.compare("PMOS") == 0)
        m1 = insertHorizontalM1(contacts, 0, "DOWN");
    else
        m1 = insertHorizontalM1(contacts, cell->gndRectItem->y(), "UP");

    fixContactsPosition(contacts, m1);

    m1->bottomRight.setY(Rules::getRule("M1.W.1"));
    m1->setY(m1->y() + (Rules::getRule("CO.W.1") + Rules::getRule("M1.E.1")*2 - Rules::getRule("M1.W.1"))/2);

    cell->m1Items->append(m1);
}

QList<Metal*>* Routing1::insertContacts(QString net, QList<Transistor*> *transistors)
{
    QList<Metal*> *contacts = new QList<Metal*>();

    foreach(Transistor *t, *(transistors))
    {
        qreal x = getContactPosition(net,transistors, t);

        if(x)
        {
            Metal* co = new Metal();

            co->band = t->transistorType;
            co->net = net;
            co->metalType = "CO";
            co->bottomRight = QPointF(Rules::getRule("CO.W.1"), Rules::getRule("CO.W.1"));

            contacts->append(co);
            co->setX(x - Rules::getRule("CO.W.1")/2);
        }
    }
    return contacts;
}

qreal Routing1::getContactPosition(QString net, QList<Transistor*> *transistors, Transistor* t)
{

    Transistor* prev = cell->getTransistorByPosIndex(transistors, t->posIndex -1);
    Transistor* next = cell->getTransistorByPosIndex(transistors, t->posIndex +1);

    if(!prev)
        prev = cell->getTransistorByPosIndex(transistors, t->posIndex -2);

    if(!next)
        next = cell->getTransistorByPosIndex(transistors, t->posIndex +2);

    //if(t->gateNetName.compare(net) == 0)
      //  return t->getGatePos().x();

    if(t->sourceNetName.compare(net) == 0)
    {
        if(!t->flipped)
        {
            if(!prev)
                return t->getSourceContPos().x();
        }
        else
        {
            if(!next)
                return t->getSourceContPos().x();
            else
                return (next->x() + t->x())/2;
        }
    }

    if(t->drainNetName.compare(net) == 0)
    {
        if(t->flipped)
        {
            if(!prev)
                return t->getDrainContPos().x();
        }
        else
        {
            if(!next)
                return t->getDrainContPos().x();
            else
                return (next->x() + t->x())/2;
        }
    }

    return 0;
}

void Routing1::fixContactsPosition(QList<Metal*> *contacts, Metal* m1)
{
    foreach(Metal* co, *(contacts))
        co->setY(m1->y() + Rules::getRule("M1.E.1"));
}

Metal* Routing1::insertHorizontalM1(QList<Metal*> *contacts, qreal initialY, QString direction)
{
    Metal *m1 = new Metal();

    m1->bottomRight = QPointF(contacts->last()->x() - contacts->first()->x() + Rules::getRule("CO.W.1"), Rules::getRule("CO.W.1") + Rules::getRule("M1.E.1")*2);
    m1->metalType = "M1";
    m1->net = contacts->first()->net;
    m1->setPos(contacts->first()->x(), initialY);

    fixMetalPosition(m1,cell->m1Items, Rules::getRule("M1.S.1"), direction);

    m1->linkedMetal->append(*contacts);
    return m1;
}

void Routing1::inflateMetal(Metal *m1, qreal rule, qreal p)
{
    qreal w = m1->bottomRight.x();
    qreal h = m1->bottomRight.y();

    m1->bottomRight.setX(w + rule*2 -p);
    m1->setX(m1->x()-rule +p/2);

    m1->bottomRight.setY(h + rule*2 -p);
    m1->setY(m1->y()-rule +p/2);
}

void Routing1::deflateMetal(Metal *m1, qreal rule, qreal p)
{
    inflateMetal(m1, -rule, -p);
}

Metal* Routing1::getCollidingMetal(Metal *m, QList<Metal*> *items, qreal spacingRule)
{
    qreal p = 0.001;
    inflateMetal(m, spacingRule, p);

    foreach(Metal* mi, *(items))
    {
        if(mi->collidesWithItem(m) && m->net.compare(mi->net) != 0)
        {
            deflateMetal(m, spacingRule, p);
            return mi;
        }
    }
    deflateMetal(m, spacingRule, p);
    return 0;
}

QStringList* Routing1::getInternNets(QList<Transistor*> *transistors)
{
    QStringList *internNets = new QStringList();
    QStringList *loneContacts = new QStringList();

    foreach(Transistor *t, *(transistors))
    {
        if(cell->countContacts(t,transistors) == 1)
            loneContacts->append(cell->getLeftNet(t));

        if(isInternNet(t->sourceNetName, transistors))
            internNets->append(t->sourceNetName);

        if(isInternNet(t->drainNetName, transistors))
            internNets->append(t->drainNetName);
    }

    internNets->removeDuplicates();

    foreach(QString net, *(loneContacts))
        internNets->removeOne(net);

    delete loneContacts;
    return internNets;
}

bool Routing1::isInternNet(QString netName, QList<Transistor*> *transistors)
{
    if(netName.compare("vcc") == 0 || netName.compare("gnd") == 0)
        return false;

    QList<Transistor*> *oppositeTransistors = cell->pTransistors;

    if(transistors->first()->transistorType.compare("PMOS", Qt::CaseInsensitive) == 0)
        oppositeTransistors = cell->nTransistors;

    foreach(Transistor *t, *(oppositeTransistors))
    {
        if(t->gateNetName.compare(netName)   == 0 ||
           t->sourceNetName.compare(netName) == 0 ||
           t->drainNetName.compare(netName)  == 0)
           return false;
    }

    foreach(Transistor *t, *(transistors))
        if(t->gateNetName.compare(netName) == 0)
           return false;

    return true;
}
